Sorting is a very common and very classic problem, the following several kinds of sorting algorithm:

Bubble sort

Bubble sort is one of the best understand algorithm, in ascending order, for example, is the smallest in the front, to a traversal of array, if the adjacent two Numbers than in front of the back of the big, to exchange their position, for the first time will traverse the biggest digital row till the last, the second will traverse the second-largest number to the penultimate place… And so on, n minus one goes all the way through the array. Detailed reference www.runoob.com/w3cnote/bub… :

Here we ourselves to implement a code:

const array = [1, 3, 2, 6, 4, 5, 9, 8, 7];

const sort = (arr) => {
  let result = [...arr];
  let temp;
  for(let i = 0; i < result.length - 1; i++){
    for(let j = 0; j < result.length - 1 -i; j++){
      if(result[j] > result[j + 1]){
        temp = result[j];
        result[j] = result[j + 1];
        result[j + 1] = temp;
      }
    }
  }
  
  return result;
}

const newArr = sort(array);
console.log(newArr); // [1, 2, 3, 4, 5, 6, 7, 8, 9]
Copy the code

Insertion sort

Poker students should be very familiar with this sorting method, each time to touch the cards have been in order to hand inside the card inside the comparison, find its position, insert. This lookup can use binary lookup, so it’s faster. Concrete analysis look here: www.runoob.com/w3cnote/ins…

const array = [1, 3, 2, 6, 4, 5, 9, 8, 7]; const sort = (arr) => { let result = [...arr]; let temp; for(let i = 0; i < result.length; i++){ let j = i; while(result[j - 1] > result[j] && j>=0){ temp = result[j - 1]; result[j - 1] = result[j]; result[j] = temp; j--; } } return result; } const newArr = sort(array); console.log(newArr); / / [1, 2, 3, 4, 5, 6, 7, 8, 9] / / binary search edition of const array = [1, 3, 2, 6, 4, 5, 9, 8, 7]. const sort = (arr) => { let result = [...arr]; let i = 0; let length = result.length; for(i; i < length; i++) { let left = 0; let right = i - 1; let current = result[i]; While (left <= right) {let middle = parseInt((left + right) / 2); if(current < result[middle]){ right = middle - 1 } else { left = middle + 1; }} for(let j = i-1; j >= left; j--){ result[j+1] = result[j]; Result [left] = current; } return result; } const newArr = sort(array); console.log(newArr); // [1, 2, 3, 4, 5, 6, 7, 8, 9]Copy the code

Quick sort

Quicksort is a highly efficient and frequently used sort in interviews. Its average time complexity is O(nlogn) and its worst time complexity is O(n^2). His core idea was to take a reference value x, and put the value less than x on the left, and the value greater than x on the right. Suppose we have the following array:

const a = [3, 6, 2, 1, 4, 5, 9, 8, 7];
Copy the code

We take the first value of the array x every time, and put the smaller value to the left, and the larger value to the right. Here, our first value is 3, and after this operation, we want to get an array that looks something like this:

const a = [2, 1, 3, 6, 4, 5, 9, 8, 7];
Copy the code

Notice in this array, everything to the left of 3 is less than 3, and everything to the right of 3 is more than 3, so the order in the left and right might not be right, but 3 itself is in the right place. How do you do that? We store 3 with x, and then use two Pointers I and j to the beginning and end of the array, respectively. Initial state x = 3, I = 0, j = 8.

0

1

2

3

4

5

6

7

8

**

3

**

6

2

1

4

5

9

8

7

We temporarily saved a[0], which is equivalent to digging out a[0], we need to find a number to fill in. Let’s work backwards, find a number less than 3, and we find that a[3] is 1(j=3), less than 3, and fill it in the hole for a[0]. Notice that I is equal to 0 and j is equal to 3.

0

1

2

3

4

5

6

7

8

**

1

**

6

2

**

1

**

4

5

9

8

7

A [3] is filled in the position of A [0], which is equivalent to a[3] is dug out again, and a number needs to be found to fill. This time we look backwards, looking for a number greater than x, and we find that a[1] is 6(I =1), greater than x, and fill it in at a[3]. Notice that I =1 and j=3.

0

1

2

3

4

5

6

7

8

1

**

6

**

2

**

6

**

4

5

9

8

7

At this time, a[1] is filled in the position of A [3], which is equivalent to a[1] is dug out again, and the number can be filled again. We continue to look for a small one from the position of J. We find that a[2] is less than 3, and we fill a[2] into a[1]. Notice that I =1, j=2;

0

1

2

3

4

5

6

7

8

1

**

2

**

**

2

**

6

4

5

9

8

7

A [2] fills a[1], and a[2] is empty again. We continue to fill it with a large number from front to back. I starts to increase, but after it increases by one, it is no less than j. So that means we’ve gone through the entire array, and we’re done. Note that if I increments once, it is not less than j, triggering the end of the loop condition, where I = 2. In this case, I is where x should have been originally cached, and we put x in a[I].

0

1

2

3

4

5

6

7

8

1

2

**

3

**

6

4

5

9

8

7

At this point, a loop finds where the reference value should be and adjusts the array so that everything to the left of the reference value is smaller and everything to the right is larger. So let’s implement this method.

const partition = (arr) => { let x = arr[0]; let length = arr.length; let i = 0; let j = length - 1; While (I < j &&arr [j] > x) {j--; while(I < j & arr[j] > x) {j--; } / / found, the value to fill in the pit, a [j] has now become a pit the if (I < j) {a [I] = a, [j]. While (I < j &&arr [I] < x) {I ++; If (I < j) {a[j] = a[I]; if(I < j) {a[j] = a[I]; }} // insert the base value into the pit a[I] = x; return arr; } const a = [2, 1, 3, 6, 4, 5, 9, 8, 7]; // let result = partition(a); console.log(result); // [1, 2, 3, 6, 4, 5, 9, 8, 7]Copy the code

By recursively calling the adjustment method to the left and right of the base value, you get every number in the array in the right place. This is called quicksort. This idea is called divide-and-conquer. The previous method of adjusting the array needs to be tweaked so that it accepts the starting and ending positions and returns the base positions.

const partition = (arr, left, right) => { let x = arr[left]; let i = left; let j = right; While (I < j &&arr [j] > x) {j--; while(I < j & arr[j] > x) {j--; } / / found, the value to fill in the pit, a [j] has now become a pit the if (I < j) {a [I] = a, [j]. While (I < j &&arr [I] < x) {I ++; If (I < j) {a[j] = a[I]; if(I < j) {a[j] = a[I]; }} // insert the base value into the pit a[I] = x; return i; } const quickSort = (arr, left, right) => { const length = arr.length; const start = left || 0; const end = right ! == undefined ? right : length - 1; if(start < end) { const index = partition(arr, start, end); quickSort(arr, start, index - 1); // quickSort(arr, index + 1, end); } return arr; } const a = [2, 1, 3, 6, 4, 5, 9, 8, 7]; Let result = quickSort(a); console.log(result); // [1, 2, 3, 4, 5, 6, 7, 8, 9]Copy the code

Merge sort

Merge sort is easier to understand than quicksort, it’s also O(nlogn), and the idea is divide-and-conquer. Suppose we already have two ordered arrays.

const a = [1 ,2, 6, 8];
const b = [3, 4, 9];
Copy the code

We now write a method to obtain the ordered array of a and b. This method is very simple. Use two Pointers I and j to each array, and then start iterating, comparing the size of a[I] and a[j] and putting the smaller one into the new ordered array. When any array is iterated through, the loop ends, and all the remaining values are placed in the new ordered array:

const merge = (arr1, arr2) => { const length1 = arr1.length; const length2 = arr2.length; const newArr = []; let i = 0; let j = 0; while(i < length1 && j < length2) { if(arr1[i] <= arr2[j]) { newArr.push(arr1[i]); i++; } else { newArr.push(arr2[j]); j++; If (I === length2) {while(j < length2) {newarr.push (arr2[j]); j++; }} if(j === I < length1) {while(I < length1) {newarr.push (arr1[I]); i++; } } return newArr; } // Const a = [1,2, 6, 8]; const b = [3, 4, 9]; const result = merge(a, b); console.log(result); // [1, 2, 3, 4, 6, 8, 9]Copy the code

Then we recursively divide the sorted array into left and right arrays until the sorted array contains only one element. Since the sorted array contains only one element, we can consider it to be ordered.

const mergeSort = (arr) => { const length = arr.length; if(length <= 1) { return arr; } const middle = Math.floor(length / 2); const left = arr.slice(0, middle); const right = arr.slice(middle); return merge(mergeSort(left), mergeSort(right)); } // Test const a = [2, 1, 3, 6, 4, 5, 9, 8, 7]; // test let result = mergeSort(a); console.log(result); // [1, 2, 3, 4, 5, 6, 7, 8, 9]Copy the code

At the end of this article, thank you for your precious time to read this article. If this article gives you a little help or inspiration, please do not spare your thumbs up and GitHub stars. Your support is the motivation of the author’s continuous creation.

Welcome to follow my public numberThe big front end of the attackThe first time to obtain high quality original ~

“Front-end Advanced Knowledge” series:Juejin. Im/post / 5 e3ffc…

“Front-end advanced knowledge” series article source code GitHub address:Github.com/dennis-jian…