There have been a lot of sorting algorithm articles, here is mainly to make a summary of their own. Most of the content is integrated from the fourth edition of algorithms, and most of the illustrations are from cainiaotuo.com. The language of choice is JavaScript. The code can be found directly in LeetCode 912. Sort array problems on the run

To do so, define a function that swaps two elements of an array

function swap(arr, i, j) {
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}
Copy the code

1. Bubble sort (easy)

process

Compare adjacent elements. Swap if the former is greater than the latter
Do the same for each pair of adjacent elements, starting from the first pair to the last pair at the end. When we do that, the last element is going to be the largest number
Repeat this step for all elements except the last one
Keep repeating the above steps for fewer and fewer elements at a time until there are no more pairs to compare

graphic

code

Reference Code 1

/ * * *@param {number[]} nums
 * @return {number[]}* /
 var sortArray = function (nums) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < nums.length - i -1; j++) {
      if (nums[j] > nums[j + 1]) {
        swap(nums, j, j + 1); }}}return nums;
};
Copy the code

Refer to code 2 to optimize bubble sorting

/ * * *@param {number[]} nums
 * @return {number[]}* /
 var sortArray = function (nums) {
  for (let i = 0; i < nums.length; i++) {
    let flag = true;
    for (let j = 0; j < nums.length - i -1; j++) {
      if (nums[j] > nums[j + 1]) {
		swap(nums, j, j + 1);
        flag = false; }}if(flag) {
      return; }}return nums;
};
Copy the code

Complexity analysis

Time complexity: O(N2)O(N^2)O(N2), where NNN is the length of array; Space complexity: O(1)O(1)O(1), using constant temporary variables.

2. Selection sort (easy)

One of the simplest sorting algorithms: first find the smallest element in the array, swap it with the first element in the array, then find the smallest remaining element, swap with the second element, until the entire array is sorted. (Keep selecting the smallest element in the remaining array)

process

First, find the smallest element in the unsorted sequence and store it at the beginning of the sorted sequence
It continues to find the smallest element from the remaining unsorted elements and places it at the end of the sorted sequence
Repeat the second step until all elements are sorted

graphic

code

/ * * *@param {number[]} nums
 * @return {number[]}* /
var sortArray = function (nums) {
  for (let i = 0; i < nums.length; i++) {
    let min = i;
    // Sorted interval [0, I), unsorted interval [I +1, len)
    // Iterate over the element after I +1 to find the index of the smallest element
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[j] < nums[min]) {
        min = j;
      }
    }
    swap(nums, i, min);
  }
  return nums;
};
Copy the code

Complexity analysis

For an array of length N, selection sort requires approximately n2/2n ^ 2/2n2/2 comparisons and NNN swaps.
It has two characteristics: (1) the running time is independent of the input, (2) the data movement is minimal, and the number of swaps is linear with the size of the array

Time complexity: O(N2)O(N^2)O(N2), where NNN is the length of array; Space complexity: O(1)O(1)O(1), using constant temporary variables.

3. Insert sort (emphasis)

process

Insert a number one at a time into an ordered array, making it a longer ordered array, and after a finite number of operations, the array will be ordered

graphic

code

Reference code 1 (Interchange elements) (Ideas for the fourth edition of the algorithm)

/** * insert sort *@param {number[]} nums
 * @return {number[]}* /
var sortArray = function (nums) {
  // Select the appropriate place to insert from the element with subscript 1, since there is only one element with subscript 0 and the default is ordered
  // Sorted interval [0, I), unsorted interval [I, len)

  // Insert nums[I] into the interval [0, I) to make it an ordered array
  for (let i = 1; i < nums.length; i++) {
    // Traverse from right to left
    for (let j = i; j > 0 && nums[j] < nums[j - 1]; j--) {
      Swap the two elements as long as nums[j] is smaller than nums[j-1]
      swap(nums, j, j - 1); }}return nums;
};
Copy the code

Reference Code 2 (Moving elements)

/** * insert sort *@param {number[]} nums
 * @return {number[]}* /
var sortArray = function (nums) {
  for (let i = 1; i < nums.length; i++) {
    // Sorted interval [0, I), unsorted interval [I, len)
    // Insert nums[I] into the interval [0, I) to make it an ordered array

    // Hold the element temporarily, then move the previous elements one by one, leaving space
    let temp = nums[i];
	let j = i;
    while(j > 0 && temp < nums[j - 1]) {
      // If nums[j] is smaller than nums[j-1], move nums[j-1] to nums[j]
      nums[j] = nums[j - 1];
      j--;
    }
    
    // find position j and place the value of I on j
    nums[j] = temp;
  }
  return nums;
};
Copy the code

Complexity analysis

Insert sort works well for partially ordered arrays and “short arrays”

Time complexity: O(N2)O(N^2)O(N2), where NNN is the length of array; Space complexity: O(1)O(1)O(1), using constant temporary variables.

4. Hill sort (Understand)

Improvements to insert sort! The reason why insertion sort is inefficient is that it only swaps adjacent elements. The idea of Hill sort is to make any element in the array with h interval be ordered, that is, to use insertion sort with interval

process

Setting the delta sequence is a hyperparameter and requires experience. The following code shows two ways to define it

graphic

code

Setting the delta sequence is a hyperparameter and requires experience. The following code shows two ways to define it

Reference Code 1 (Exchange elements)

var shellSortArray = function (nums) {
  const N = nums.length;
  // Use the Knuth delta sequence
  let h = 1;
  while (h < N / 3) {
    h = 3 * h + 1; // Dynamically define interval sequences
  }

  while (h >= 1) {
    for (let i = h; i < N; i++) {
      for (let j = i; j >= h && nums[j] < nums[j - h]; j -= h) {
        swap(nums, j, j - h);
      }
    }
    h = Math.floor(h / 3)}};Copy the code

Reference Code 2 (Moving elements)

var shellSortArray2 = function (nums) {
  const N = nums.length;
  for (let gap = N / 2; gap > 0; gap = Math.floor(gap/2)) {
    for (let i = gap; i < N; i++) {
      let temp = nums[i];
      let j = i;
      while(j >= gap && nums[j - gap] > temp){ nums[j] = nums[j - gap]; j -= gap; } nums[j] = temp; }}return nums;
};
Copy the code

Complexity analysis

In the case of entering a randomly sorted array, we do not know mathematically the average number of comparisons required for Hill sorting

5. Merge sort (emphasis)

Merges two ordered arrays into a larger ordered array

process

Divide-and-conquer algorithm, recursive call

Apply for a space equal to the sum of two sorted sequences, which is used to store the combined sequence;
Set two Pointers, starting at the start of two sorted sequences;
Compare the elements pointed to by the two Pointers, select the smaller element into the merge space, and move the pointer to the next position;
Repeat step 3 until a pointer reaches the end of the sequence;
Copies all remaining elements of the other sequence directly to the end of the merged sequence.

graphic

code

Using the queue method of arrays in JavaScript makes merge sort surprisingly easy to implement without too many pointer problems

/** * merge sort algorithm *@param {*} Array arr *@returns Ordered array */
function mergeSort(arr) {
  // Use top-down recursion
  const N = arr.length;
  if (N < 2) {
    // Return the array with only one element
    return arr;
  }
  // x >> 1 === math.floor (x / 2) // x >> 1 === math.floor (x / 2)
  // N >> 1 is equivalent to math.floor (N / 2)
  let middle = N >> 1;
  // Split into two subarrays
  let left = arr.slice(0, middle);
  let right = arr.slice(middle);
  // Recursive call mergeSort
  return merge(mergeSort(left), mergeSort(right));
}


/** * merge two ordered arrays *@param {*} Left left array *@param {*} Right Right array *@returns An ordered array temp */
function merge(left, right) {
  // Temporary arrays store merged data
  const temp = [];
  // Neither array has been traversed yet
  while (left.length && right.length) {
    // Note: the judgment condition is less than or equal to, if only less than, then the sorting will be unstable.
    if (left[0] <= right[0]) {
      // left[0] is small, delete left[0] from left array, and place it in temp array
      temp.push(left.shift());
    } else {
      // Delete the first item in the right array and place it in the temp arraytemp.push(right.shift()); }}// Left array still has elements, right array traversed
  while (left.length) {
    // Place the remaining elements of the left array in the temp array
    temp.push(left.shift());
  }
  // The left array is iterated
  while (right.length) {
    temp.push(right.shift());
  }
  // Returns the sorted array
  return temp;
}

Copy the code

Instead of using some of the Array methods that come with JavaScript, we’ll rewrite the pointer approach as described in Algorithms (4th Edition)

/** * sort the array *@param {number[]} nums
 * @return {number[]}* /
var sortArray = function (nums) {
  const N = nums.length;
  let temp = new Array(a); mergeSort(nums,0, N - 1, temp);
  return nums;
};

/** * merge sort uses a top-down recursive method *@param {number[]} nums
 * @param {number} left
 * @param {number} right
 * @param {number[]} temp
 * @returns* /
var mergeSort = function (nums, left, right, temp) {
  // Return if Pointers overlap
  if (left >= right) {
    return;
  }

  // let mid = Math.floor(left + (right - left) / 2);
  let mid = (left + right) >> 1;
  // Recursive call mergeSort
  mergeSort(nums, left, mid, temp);
  mergeSort(nums, mid + 1, right, temp);
  // Merge two ordered arrays
  merge(nums, left, mid, right, temp);
};

/** * merges two ordered arrays *@param {number[]} nums
 * @param {number} left
 * @param {number} mid
 * @param {number} right
 * @param {number[]} temp* /
var merge = function (nums, left, mid, right, temp) {
  // Copy nums to temp
  for (let k = left; k <= right; k++) {
    temp[k] = nums[k];
  }

  // Define a pointer to each array
  let i = left;
  let j = mid + 1;

  // Write elements in temp back to nums as a rule
  for (let k = left; k <= right; k++) {
    if (i > mid) {
      // Take the left half, take the right half
      nums[k] = temp[j];
      j++;
    } else if (j > right) {
      // Take the left half of the element and move the left pointer to the right
      nums[k] = temp[i];
      i++;
    } else if (temp[i] <= temp[j]) {
      // The left side is smaller
      nums[k] = temp[i];
      i++;
    } else {
      / / on the right side of the smallnums[k] = temp[j]; j++; }}};Copy the code

Complexity analysis

Time complexity: O(Nlog⁡N)O(N \log N)O(NlogN), where NNN is the length of the array; Space complexity: O(N)O(N)O(N), the size of the auxiliary array is the same as that of the input array.

To optimize the

Set the short array length threshold so that insertion sort is used when merging into short arrays

The above is a top-down recursive method, and there is also a bottom-up recursive method, which will not be introduced here. For details, please refer to the fourth edition of the algorithm

6. Quicksort (emphasis)

process

Choose a value from the array as the pivot, the value in the middle of the array.
Create two Pointers (references), one on the left to the first value of the array and one on the right to the last value of the array. Move the left pointer until we find a value greater than the pivot, then move the right pointer until we find a value less than the pivot, then swap them and repeat the process until the left pointer passes the right. This process will place any value less than the pivot before the pivot, and any value greater than the pivot after it. This step is called a partition operation.
The algorithm repeats the previous two steps for the partitioned small array (a subarray of values smaller than the pivot and a subarray of values larger than the pivot) until the array is completely sorted.

graphic

code

Double pointer method

/ * * *@param {number[]} nums
 * @return {number[]}* /

var sortArray = function (nums) {
  const N = nums.length;
  quickSort(nums, 0, N - 1);
  return nums;
};

function quickSort(nums, left, right) {
  if (right <= left) {
    return;
  }
  let pIndex = partition(nums, left, right);
  quickSort(nums, left, pIndex - 1);
  quickSort(nums, pIndex + 1, right);
}

function partition(nums, left, right) {

  let pivot = nums[left];
  // Define a pointer to each array
  let i = left + 1;
  let j = right;

  while (true) {
    while (i <= right && nums[i] <= pivot) {
      i++;
    }
    while (j > left && nums[j] > pivot) {
      j--;
    }
    if (i >= j) {
      break;
    }
    swap(nums, i, j);
    i++;
    j--;
  }
  swap(nums, left, j);
  return j;
}
Copy the code

Complexity analysis

Time complexity: O(Nlog⁡N)O(N \log N)O(NlogN), where NNN is the length of the array; Space complexity: O(log⁡N)O(\log N)O(logN), where the space occupied is mainly from the stack space of recursive functions.

7. Heap sort (emphasis)

concept

So what is a heap

A binary tree is called heap-ordered when each node is greater than or equal to two of its children. The root is the largest node in a heap-ordered binary tree a complete binary tree of size N has height [lgN]

Big top heap: Logically a complete binary tree, for any node in the tree, the value of the key is not less than the value of the key of its child node.

Some operations on the heap

The parent node is I, its left child node is 2i+1, and its right child node is 2i+2. The last non-leaf node is numbered [n/2] -1 (rounded down). In a heap, the parent node of the node at position K is [k/2], Its two children are at positions 2k and 2k+1. One layer up from a[k] makes k equal to k/2, and one layer down makes k equal to 2k or 2k+1

One of the more interesting descriptions I read in the book

If we think of the heap as a tight underworld organization, where each child represents a subordinate (and the parent represents its immediate superior), these operations can be explained in interesting ways. A talented newcomer joins the organization and is promoted through the ranks until he meets a stronger leader. When the leader of an entire community retires and is replaced by an outsider, if his subordinates are better than he is, their roles will be switched, and this will continue until he is better than his subordinates.

function swim(k){
  while(k > 1 && nums[Math.floor(k/2)] < nums[k]){
    swap(nums, Math.floor(k/2), k);
    k = Math.floor(k/2); }}Copy the code

function sink(k){
  while(2*k <= N) {
    let j = 2 * k;
    if(j < N && nums[j] < nums[j+1]){
      j++;
    }
    if(nums[k] >= nums[j]){
      break; } swap(nums, k, j); k = j; }}Copy the code

1. Build the heap

Find the last nonleaf node [n/2] -1 in a complete binary tree
Compare the size of this node with that of its child. If it is smaller than the maximum value of the child, swap their values
Keep moving up (minus one) repeat step 2

2. Insert the node

The node to be inserted is placed at the end of all nodes
Find a path from this node to the root node, if larger than the parent node, swap until no larger than the parent node

3. Delete the node

Remove the node to be deleted
Replace the node to be deleted with the last node in the heap
Make similar adjustments to the swapped nodes as described in Step 2

process

Heap sorting can be divided into two phases. In the construction phase of the heap, we reorganize the original arrays into a heap; Then in the sink sort phase, we fetch all the elements from the heap in descending order and get the sorting result.

Initialize the keyword sequence to be sorted (R1,R2…. Rn)(R_1, R_2 …. R_n)(R1,R2…. Rn) is constructed into the big top heap, which is the initial unordered region; [Reorder of the heap]
The top element R[1] is swapped with the last element R[n], and a new unordered region (R1,R2….) is obtained Rn) – 1) (R_1, R_2… R_{n-1})(R1,R2…. Rn) – 1) and new area (Rn) (R_n) (Rn), and meet the R [1, 2… n – 1) < = R [n] R [1, 2… n – 1) < = R [n] R [1, 2… n – 1) < = R [n].
Since the new heap top R[1] after the swap may violate the heap properties, it is necessary for the current unordered region (R1,R2…. Rn) – 1) (R_1, R_2… R_{n-1})(R1,R2…. Rn−1) adjusts to the new heap, and then swaps R[1] again with the last element of the unordered region, yielding the new unordered region (R1,R2…. Rn – 2) (R_1, R_2… R_{n-2})(R1,R2…. Rn−2) and the new ordered region (Rn−1,Rn)(R_{n-1}, R_n)(Rn−1,Rn). This process is repeated until the number of ordered elements is N − 1n-1n −1, and the whole sorting process is complete.

graphic

code

/** * heap sort *@param {*} nums
 * @returns* /
function sortArray(nums) {
  const N = nums.length;
  // Build a heap to find the first non-leaf node, traverse up
  for (let i = Math.floor(N / 2 - 1); i >= 0; i--) {
    // Adjust the heap for the I node
    heapify(nums, i, N);
  }
  // Each time the sorting process finds the current maximum (root node), and the array length is reduced by one
  for (let i = N - 1; i > 0; i--) {
    // Switch the root node to the last node (move the largest element at this point to the end of the array)
    swap(nums, 0, i);
    // Adjust the last element of the heap to the root node
    heapify(nums, 0, i);
  }
  return nums;
}

/** * Adjust the heap on node I * satisfy: the child heap below node I is a large top heap * adjust range [I, length] *@param {*} nums
 * @param {*} i
 * @param {*} length* /
function heapify(nums, i, length) {
  // Save the value of the I node. This process is to find a suitable location for temp
  let temp = nums[i]
  // j points to the left child node of I
  let j = 2 * i + 1;
  // loop over [I, length]
  while (j < length) {
    if (j + 1 < length && nums[j] < nums[j + 1]) {
      // The parent node has a right child and the left child is smaller than the right child
      j++;
    }
    // j points to the larger of the child nodes of I
    if (temp < nums[j]) {
      // If the parent is smaller than the j node
      // Swap the elements of I and j
      swap(nums, i, j);
      // Move both I and j down one bit
      i = j;
      j = 2 * i + 1; 
    } else {
      // If the parent node is larger than the largest element in the child node, it exits the loop
      break; }}}Copy the code

Complexity analysis

Heap sort consists of two operations: heap build and sort. The time complexity of heap build is O(N)O(N)O(N) O(N)O(N)O(N \log N)O(NlogN) O(Nlog⁡N)O(N \log N)O(NlogN) The overall time complexity of heap sort is O(Nlog⁡N)O(N \log N)O(NlogN).

8. Counting sort (Understand)

process

Find the largest and smallest elements in the array to be sorted
Count the number of occurrences of each element of value I in the array, stored in the i-th entry of array C
Add up all the counts (starting with the first element in C, adding each term to the previous one)
Reverse populating the target array: place each element I in the C(I) item of the new array, subtracting C(I) by 1 for each element

graphic

code

function countingSort(arr, maxValue) {
    var bucket = new Array(maxValue+1),
        sortedIndex = 0;
        arrLen = arr.length,
        bucketLen = maxValue + 1;

    for (var i = 0; i < arrLen; i++) {
        if(! bucket[arr[i]]) { bucket[arr[i]] =0;
        }
        bucket[arr[i]]++;
    }

    for (var j = 0; j < bucketLen; j++) {
        while(bucket[j] > 0) { arr[sortedIndex++] = j; bucket[j]--; }}return arr;
}
Copy the code

9. Radix sort (Understand)

graphic

code

//LSD Radix Sort
var counter = [];
function radixSort(arr, maxDigit) {
    var mod = 10;
    var dev = 1;
    for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        for(var j = 0; j < arr.length; j++) {
            var bucket = parseInt((arr[j] % mod) / dev);
            if(counter[bucket]==null) {
                counter[bucket] = [];
            }
            counter[bucket].push(arr[j]);
        }
        var pos = 0;
        for(var j = 0; j < counter.length; j++) {
            var value = null;
            if(counter[j]! =null) {
                while((value = counter[j].shift()) ! =null) { arr[pos++] = value; }}}}return arr;
}
Copy the code

10. Bucket sorting (Understand)

code

function bucketSort(arr, bucketSize) {
    if (arr.length === 0) {
      return arr;
    }

    var i;
    var minValue = arr[0];
    var maxValue = arr[0];
    for (i = 1; i < arr.length; i++) {
      if (arr[i] < minValue) {
          minValue = arr[i];                // The minimum value of input data
      } else if (arr[i] > maxValue) {
          maxValue = arr[i];                // The maximum value of the input data}}// Initialize the bucket
    var DEFAULT_BUCKET_SIZE = 5;            // Set the default number of buckets to 5
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;  
    var buckets = new Array(bucketCount);
    for (i = 0; i < buckets.length; i++) {
        buckets[i] = [];
    }

    // Allocate data to buckets using mapping functions
    for (i = 0; i < arr.length; i++) {
        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
    }

    arr.length = 0;
    for (i = 0; i < buckets.length; i++) {
        insertionSort(buckets[i]);                      // Sort each bucket, using insert sort
        for (var j = 0; j < buckets[i].length; j++) { arr.push(buckets[i][j]); }}return arr;
}
Copy the code

Radix sort: buckets are allocated according to each digit of the key value;
Counting sort: each bucket stores a single key;
Bucket sorting: Each bucket stores a range of values;

【 Algorithm 】 Summary of classical sorting algorithm -JavaScript description – graphic – complexity analysis – insert – fast – merge – heap sort, etc

1. Bubble sort (easy)

process

graphic

code

Complexity analysis

2. Selection sort (easy)

process

graphic

code

Complexity analysis

3. Insert sort (emphasis)

process

graphic

code

Complexity analysis

4. Hill sort (Understand)

process

graphic

code

Complexity analysis

5. Merge sort (emphasis)

process

graphic

code

Complexity analysis

To optimize the

6. Quicksort (emphasis)

process

graphic

code

Complexity analysis

7. Heap sort (emphasis)

concept

1. Build the heap

2. Insert the node

3. Delete the node

process

graphic

code

Complexity analysis

8. Counting sort (Understand)

process

graphic

code

9. Radix sort (Understand)

graphic

code

10. Bucket sorting (Understand)

code

11. A summary

Related Posts

Antmove Cross-side development: cross-side syntax and conditional compilation

Micro front end – Summary of technical solutions

Vue multicast components