1. Bubble sort

1.1 the principle

Bubble sort is one of the simplest sorts, described in one sentence

Find the largest element in the unordered region by swapping, and put it in front of the ordered region

Take the unordered array [3,2,4,1] as an example. If you rank the maximum value to the end, you get [3,2,1,4]. [3,2,1] is the unordered range, and [4] is the ordered range.

thisexchangeHow do you understand that? Let’s look at a picture

Or in the,2,4,1 [3]This array, for example,

  1. To compare3and2.3If I switch the two positions, I get,3,4,1 [2]
  2. Continue to compare3and4.4If I don’t do anything, I get,3,4,1 [2]
  3. To compare4and1.4If I switch the two positions, I get,3,1,4 [2].

After completing this round of traversal, you can see that you have moved the maximum 4 to the far right.

You can then repeat the above process for [2,3,1] in the disordered region, slowly expanding the ordered region until the disordered region is empty. To complete this process, there are approximately four rounds of traversal, which are for [2,3,4,1], [2,3,1], [1,2], and [1].

1.2 Complexity and stability

Complexity can be divided into time complexity and extra space complexity. For more information, refer to the time and space complexity of the algorithm.

Next, we deduce the time complexity of bubble sort:

1.2.1 Time Complexity

In our example, we made three comparisons of [2,3,4,1] in the first round of traversal. In the other three rounds of traversal, [2,3,1], [1,2] and [1] are compared twice, once and zero times respectively. If the length of the array is N, the total number of executions is


O = ( N – 1 ) + ( N – 2 ) + ( N – 3 ) + . . . + 1 O = (N – 1) + (N – 2) + (N – 3) + … + 1

It’s not hard to see that it’s the sum of the arithmetic sequence, and the arithmetic sequence is summed by


S ( n ) = ( a 0 + a n ) n 2 S(n) = \frac{(a_0 + a_n) n}{2}

By using the formula


O = ( 1 + N – 1 ) N 2 = N 2 2 O = \frac{(1 + N – 1)N}{2} = \frac{N^2}{2}

So the time complexity is O(N2)O(N^2)O(N2).

1.2.2 Extra space complexity

The extra space required for bubble sort does not vary with the size of some variable n, so its space complexity is O(1).

1.2.3 stability

Stability refers to whether two elements of the same value change before and after the array sorting process. For more information, refer to the stability of the sorting algorithm.

In the bubble sort process, when comparing the same two values, you can not change the position of the two values, so it is stable. You can understand this conclusion in combination with the above example.

1.3 Code implementation

fuction bubleSort(arr) {
  var len = arr.length;
  for (var i = len - 1; i >= 0; i -= 1) {
    for (var j = 0; j < i; j += 1) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1)}}}return arr;
}

function swap(arr, i, j) {
    if (i === j) return;
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}

Copy the code

The swap function swap is used to swap the values of positions I and j in array ARr via xOR (^). For those who are not interested in this section, go ahead and read the chapter summary.

The opposite of x or is y or.

Because it’s not used very often, ninety percent of people won’t remember the difference. The author provides a relatively easy to remember formula, different or non-carry binary addition.

Xor has the following mathematical laws:

(a ^ b) ^ c = a ^ (b ^ c) = a ^ (b ^ c)

Arr [j]=arr[I]arr[J]=arr[I]arr[j]=arr[I]arr[j]=arr[I]

arr[i] = arr[i] ^ arr[j]
arr[j] = arr[i] ^ arr[j]
Copy the code

If you substitute the first expression into the second expression, you get

arr[j] = (arr[i] ^ arr[j]) ^ arr[j]
       = arr[i] ^ (arr[j] ^ arr[j])
       = arr[i] ^ 0
       = arr[i]
Copy the code

Arr [I]=arr[J]arr[I]=arr[J]arr[I]=arr[J]

arr[i] = arr[i] ^ arr[j]
arr[j] = arr[i]
arr[i] = arr[i] ^ arr[j]
Copy the code

If you substitute the first two into the third, you get

arr[i] = (arr[i] ^ arr[j]) ^ arr[i]
       = (arr[i] ^ arr[i]) ^ arr[j]
       = 0 ^ arr[j]
       = a[j]
Copy the code

Note: Do not perform the above logic for values in the same position in the array.

1.4 Chapter summary

  1. So bubble sort can be thought of as inDisordered areathroughexchangeFind the largest element and put it inOrderly areaIn front of.
  2. Bubble sort is O(N2)O(N ^ 2)O(N2)
  3. The extra space complexity of bubble sort is O(1)O(1)O(1)
  4. Bubble sort is not stable
  5. Xor can be understood as a non-carry binary addition, which can be used to implement “SAO operations” such as array swapping

2. Select sort

2.1 the principle

Selection sort, which is a simple and intuitive sorting algorithm, can be thought of as

Find the smallest number in the unordered region and put it behind the ordered region

As an unordered array,2,4,1 [3]For example, if the lowest value is arranged in the front, you get,3,2,4 [1].[1]isOrderly area.[3, 4-trichlorobenzene]isDisordered area.Assume that the,2,4,1 [3]Start the first round of traversal

  1. Create indexesiIt points to the beginning of the array0Position, used to pointDisordered areaThe first number of
  2. traverse,2,4,1 [3], the minimum value is1, and it0Value of position3exchange
  3. Now on the leftOrderly areaNew numerical1Index I is shifted one bit to the right,Disordered areafor[3, 4-trichlorobenzene]

Repeat the above process until the disorder region is empty. To complete this process, there are approximately four iterations of [2,3,4,1], [3,2,4], [3,4], and [4].

2.2 Complexity and stability

2.2.1 Time Complexity

The time complexity derivation method of selection sort is similar to that of bubble sort. In the example, 3, 2, 1 and 0 times are compared in the 4 rounds of traversal. If the length of the array is N, the time complexity is zero


O = ( N – 1 ) + ( N – 2 ) + ( N – 3 ) + . . . + 1 O = (N – 1) + (N – 2) + (N – 3) + … + 1

By arithmetic sequence summation formula


S ( n ) = ( a 0 + a n ) n 2 S(n) = \frac{(a_0 + a_n) n}{2}

So you get the time complexity O(N2)O(N ^ 2)O(N2).

2.2.2 Extra space complexity

The extra space required for selection sort does not vary with the size of some variable n, so its space complexity is O(1).

2.2.3 stability

In the example above, when the minimum value is obtained in the unordered region, it is swapped with the leftmost value in the unordered region, and this process causes the value that was later to be put in front of it.

Therefore, it is possible for the same values in an array to switch positions, and selection sort is not stable

2.3 Code implementation

function selectSort(arr) {
  const len = arr.length;
  for (let i = 0; i < len; i++) {
    minIndex = i;
    for (let j = minIndex; j < len; j++) {
      if(arr[j] < arr[minIndex]) { minIndex = j; }}if(minIndex ! == i) { swap(arr, minIndex, i) } }return arr;
}

function swap(arr, i, j) {
    if (i === j) return;
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}

Copy the code

2.4 Summary of this chapter

  1. Selection sort fromDisordered areaFind the smallest number in theOrderly areaThe back of the
  2. Select sort in order N ^ 2 time.
  3. The extra space complexity of selection sort is O(1)
  4. Selection sort is unstable

3. Insertion sort

3.1 the principle

Sometimes it’s easy to confuse insertion sort with selection sort. Insertion sort is actually the same way we arrange cards in a poker game, and I suggest using this method to remember the sorting algorithm. Describe it in one sentence

Insert each element of the unordered region into the appropriate location of the ordered region

Again, take the unordered array [3,2,4,1] as an example

In the beginning, [3] is the ordered region, and [2,4,1] is the disordered region. Then the leftmost 2 of the unordered area is sorted in the ordered array. After comparing 2 with 3, the ordered area is [2,3] and the unordered area is [4,1]. And so on, until the disordered region is empty. To complete this process, a total of about 3 rounds of traversal are required, respectively

  1. A disorderly array,4,1 [2]In the2In an ordered array[3]In order to find the right position, getOrderly areafor[2, 3]
  2. A disorderly array(4, 1)In the4In an ordered array[2, 3]In order to find the right position, getOrderly areafor[4] 2
  3. A disorderly array[1]1 in an ordered array[4] 2In order to find the right position, getOrderly areafor[1, 2, 3, 4]

3.2 Complexity and stability

3.2.1 Time Complexity

If the array is in reverse order and the length is N, you need to compare 1 to N-1 times for each number in the unordered array to find the appropriate position in the ordered array. The maximum time complexity is


O = 1 + 2 + . . . + ( N – 2 ) + ( N – 1 ) O = 1 + 2 + … + (N – 2) + (N – 1)

So the arithmetic sequence summation formula is O(N2)O(N ^ 2)O(N2)

3.2.2 Extra space complexity

The extra space required for insertion sort does not vary with the size of some variable n, so its space complexity is O(1).

3.2.3 stability

As you can see from the figure above, inserting elements from the unordered region into the ordered region is traversed from right to left. If you have two identical values, the first sorted value is in the ordered area, and the second sorted value is ranked to the right of it, so the insertion sort is stable.

3.3 Code Implementation

function insertSort(arr) {
  for (var i = 0; i < arr.length - 1; i++) {
    var minIndex = i;
    for (var j = i + 1; j < arr.length; j++) {
      if (arr[minIndex] > arr[j]) {
        minIndex = j;
      }
    }
    swap(arr, i, minIndex);
  }
  return arr;
}

function swap(arr, i, j) {
  if (i === j) {
    return;
  }
  arr[i] = arr[i] ^ arr[j];
  arr[j] = arr[i] ^ arr[j];
  arr[i] = arr[i] ^ arr[j];
}

Copy the code

3.4 Chapter summary

  1. Insertion sort is similar to playing cardsDisordered areaOf each element inserted intoOrderly areaIn the right place
  2. Insertion sort is O(N2)O(N ^ 2)O(N2)
  3. The extra space complexity of insertion sort is O(1)O(1)O(1)
  4. Insertion sort is stable