Summary of ten classic sorting algorithms

Algorithm to compare

Each algorithm has its own time complexity and stability characteristics. The following is a comparison chart of common indicators of the ten classic algorithms

Algorithm indicators

Time complexity

When we compare the advantages and disadvantages of the algorithm, the limited consideration is to compare the time complexity, commonly used O notation. I’m not going to overstate it here.

Please note that when our O indexes are the same, that is to say, the grade is the same, we cannot compare them by constant terms. There is no proportional relationship between them, which can only be determined by actual calculation.

Such two expressions for example, a = > O (N ^ 2 + 200 9999 N) and b = > O (N ^ 2), you can’t say b is better, this was associated with the function of specific operations, for example, if the b is constant + – * / operations, such as constant but a running ^ | & arithmetic operations, such as Obviously bits are better than constants. This is where the constant index 9999 becomes a bit of a chicken.

Algorithm content

Bubble sort

Algorithm steps

• Compare adjacent elements. If the first one is bigger than the second, swap them both.

• 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

Images demonstrate

Code implementation

function swap(arr, i, j) {
  var temp = arr[j];
  arr[j] = arr[i];
  arr[i] = temp;
}
function bubbleSort(arr) {
  var len = arr.length;
  // Total number of rounds to execute
  for (var i = 0; i < len - 1; i++) {
    // The number of comparisons per round
    for (var j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        // If the previous number is greater than the previous number, switch places
        swap(arr, j, j + 1); }}}return arr;
}
console.log(
  bubbleSort([3.5.38.15.36.26.27.2.44.46.4.19.47.48.50]) 
  / / [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
);

Copy the code

Selection sort

Selection sort is a simple and intuitive sorting algorithm, whatever data goes in is O(n²) time complexity. So when you use it, the smaller the data, the better. The only benefit might be that it doesn’t take up any extra memory.

Algorithm steps

1. First find the smallest (large) element in the unsorted sequence and store it at the beginning of the sorted sequence.

2. Find the smallest (largest) element from the remaining unsorted elements and place it at the end of the sorted sequence.

3. Repeat the second step until all elements are sorted.

Images demonstrate

Code implementation

function swap(arr, i, j) {
  var temp = arr[j];
  arr[j] = arr[i];
  arr[i] = temp;
}
function selectionSort(arr) {
  var len = arr.length;
  // Record the current minimum index
  var minIndex;
  // Total number of rounds to execute
  for (var i = 0; i < len - 1; i++) {
    minIndex = i;
    // Find the index with the smallest value for each round
    for (var j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        // If the previous number is greater than the previous number, switch places
        minIndex = j;
      }
    }
    swap(arr, i, minIndex);
  }
  return arr;
}
console.log(
  selectionSort([3.5.38.15.36.26.27.2.44.46.4.19.47.48.50]) / / [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
);
Copy the code

Insertion sort

Insertion sort is one of the most simple and intuitive sorting algorithms. Its working principle is to build an ordered sequence and scan the unsorted data from back to front in the sorted sequence to find the corresponding position and insert it. Like bubble sort, insert sort also has an optimization algorithm called split insert.

Algorithm steps

1. Treat the first element of the first to be sorted sequence as an ordered sequence and the second element to the last element as an unsorted sequence.

2. Scan the unordered sequence from beginning to end, inserting each scanned element into the appropriate place in the ordered sequence. (If the element to be inserted is equal to an element in the ordered sequence, the element to be inserted is inserted after the equal element.)

The demo

Code demo

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    // The current number to compare
    const current = arr[i];
    // Record the index of the number currently being compared
    let preIndex = i - 1;
    while (preIndex >= 0 && arr[preIndex] > current) {
      // When the number being compared is larger than the current number, move it back one bit
      arr[preIndex + 1] = arr[preIndex];
      preIndex--;
    }
    // The number found is no longer greater than the current number or has reached the end, insert the current number after the number being compared
    arr[preIndex + 1] = current;
  }
  return arr;
}
console.log(
  insertionSort([3.5.38.15.36.26.27.2.44.46.4.19.47.48.50])
  / / [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
);
Copy the code

Hill sort (understood)

Hill sort, also known as the descending incremental sort algorithm, is a more efficient and improved version of insertion sort. But Hill sort is an unstable sort algorithm.

Hill sort is an improved method based on the following two properties of insertion sort:

• Insertion sort has high efficiency when it operates on almost ordered data, that is, it can achieve the efficiency of linear sort.
• But insert sort is generally inefficient because it can only move data one bit at a time;

The basic idea of Hill sorting is that the whole sequence of records to be sorted is divided into several sub-sequences for direct insertion sorting respectively. When the records in the whole sequence are “basically ordered”, the whole records are directly inserted in sequence.

Algorithm steps

Select an incremental sequence T1, T2… , where Ti > tj, tk = 1;

Sort the sequence k times according to the number of incremental sequences k;

In each sort, the sequence to be sorted is divided into several sub-sequences of length M according to the corresponding increment TI, and each sub-table is sorted by direct insertion. Only when the increment factor is 1, the whole sequence is treated as a table, and the length of the table is the length of the whole sequence.

The demo

Code implementation

function shellSort(arr) {
  var len = arr.length,
    current,
    subAreaLen = 1;
  while (subAreaLen < len / 3) {
    // Dynamically define interval sequences
    subAreaLen = subAreaLen * 3 + 1;
  }
  for (var gap = subAreaLen; gap > 0; gap = Math.floor(gap / 3)) {
    for (var i = gap; i < len; i++) {
      current = arr[i];
      var preIndex = i - gap;
      while (preIndex >= 0&& arr[preIndex] > current) { arr[preIndex + gap] = arr[preIndex]; preIndex -= gap; } arr[preIndex + gap] = current; }}return arr;
}

console.log(
  shellSort([3.5.38.15.36.26.27.2.44.46.4.19.47.48.50])
  / / [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
);
Copy the code

Merge sort

Merge sort is an efficient sorting algorithm based on Merge operations. This algorithm is a very typical application of Divide and Conquer.

Algorithm steps

1. Apply for a space equal to the sum of two sorted sequences, which is used to store the combined sequence;
2. Set two Pointers, starting at the start of two sorted sequences;
3. 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;
4. Repeat step 3 until a pointer reaches the end of the sequence;
5. Copies all remaining elements of the other sequence directly to the end of the merged sequence.

The demo

Code implementation

function sort(arr) {
  if (arr == null || arr.length < 2) {
    return;
  }
  mergeSort(arr, 0, arr.length - 1);
  return arr;
}
function mergeSort(arr, l, r) {
  if (l === r) return;
  var m = l + ((r - l) >> 1);
  mergeSort(arr, l, m);
  mergeSort(arr, m + 1, r);
  // The merge process takes place in layers
  merge(arr, l, m, r);
}
function merge(arr, l, m, r) {
  var help = [];
  var i = 0;
  var p1 = l;
  var p2 = m + 1;
  while (p1 <= m && p2 <= r) {
    // Get some smaller value and assign it to help. Pointer back one bit
    help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
  }

  while (p1 <= m) {
    // Copy the remaining values into the help array
    help[i++] = arr[p1++];
  }

  while (p2 <= r) {
    help[i++] = arr[p2++];
  }

  for (var i = 0; i < help.length; i++) {
    arr[l + i] = help[i];
  }
  console.log("merge", arr);
}

console.log(
  sort([3.5.38.15.36.26.27])
  //[3, 5, 15, 26,27, 36, 38]
);

/** * 3, 5, 15, 26,27, 36, 38 * / \ * 3,5,15 26,27,36,38 = > merge * / \ \ * 3, 5, 15, 26, 27, 36, 38 = > merge * / \ \ / \ * 5 15 26 and 27 36 38 = > merge * /
Copy the code

Calculation of time complexity

Since recursion is a classic divide-and-conquer strategy, follow the master formula.

The master formula (also known as the master method) is a time-complexity analysis method that is often used to solve problems using divide-and-conquer strategies. There are also two commonly used recursive solutions of divide-and-conquer strategy called substitution method and recursive tree method. As we all know, solving a problem using recursion in divide-and-conquer strategy is divided into three steps, namely decomposition, solution and merger. Therefore, the main method is expressed as follows:

T [n] = aT n/b + f (n) (directly for T = [n] aT [n/b] + T (n ^ d))

Where a >= 1 and b > 1 is constant, it represents the meaning of

• nRepresents the size of the problem,
• aThe number of recursions is the number of subproblems generated,
• bIt means that each recursion is the same1/bOne scale,F (n)Represents the sum of the time taken to decompose and merge.
• dRepresents the time complexity of the subprocess

The final solution

1. whend<logb a, the time complexity isO(n^(logb a))
2. whend=logb a, the time complexity isO((n^d)*logn)
3. whend>logb a, the time complexity isO(n^d)

The sample

Our merge sort

1. ais2Because themergeSortCalled twice;
2. bis2Because we have the same number of intervals each time1/2;
3. dis1Because themergeSortAll you’re doing inside the function is shrinking the interval. Time complexity isO(n)

So the end result, merge sort is order NlogN time, order N extra space.

Quick sort

Algorithm steps

1. First find the left end of the position (random number probability event), and the right end of the number exchange (function is to swap the current number as the base number)

2. Partitioning operations

   • First, establish the less and more areas, the current number pointer, the position of the number to be compared

   • Compares the size relationship between the current number and the number being compared

     • Less than,lessThe area expands to the right, switching the positions of the two numbers, and moving the cur pointer to the right one bit
     • More than,moreThe field expands to the left, and the two numbers are swapped. The cur pointer does not move (because the swapped numbers continue to be compared)
     • It’s equal to cur and we move it one place to the right

   • The swap position between the larger range and the index being compared

   • Returns the current middle position

3. After getting the position of the middle area, recalculate the less than area and greater than area, continue to partition sort

The demo

Code implementation

function swap(arr, i, j) {
  var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

function sort(arr) {
  if(! arr || arr.length <2) {
    return;
  }
  quickSort(arr, 0, arr.length - 1);
  return arr;
}

function quickSort(arr, l, r) {
  if (l < r) {
    // Use random numbers to reduce complexity by making worst-case scenarios probabilistic
    var random = Math.floor(Math.random() * (r - l + 1));
    swap(arr, l + random, r);
    var p = partition(arr, l, r);
    // Less than the extent continues to partition sort
    quickSort(arr, l, p[0] - 1);
    // If the value is larger than the value, the partition sort continues
    quickSort(arr, p[1] + 1, r); }}function partition(arr, l, r) {
  var less = l - 1; // The index at the beginning of the "less than" area
  var more = r; // Index at the beginning of the greater than area
  var cur = l; // The index of the current comparison
  var compare = r; // The index being compared
  while (cur < more) {
    if (arr[cur] < arr[compare]) {
      // The current number is small, the < area expands to the right, swap values, the current number pointer back
      swap(arr, ++less, cur);
      cur++;
    } else if (arr[cur] > arr[compare]) {
      // If the current number is large, the > area expands to the left, swap values, the current number pointer does not move,
      swap(arr, --more, cur);
    } else {
      // If this position is equal, the pointer will continue to move furthercur++; }}// Swap positions between the greater than range and the index being compared
  swap(arr, more, compare);
  // Return to the middle area
  return [less + 1, more];
}

console.log(
  sort([3.5.38.15.36.26.27.2.44.46.4.19.47.48.50])
  / / [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
);

Copy the code

Heap sort

Algorithm steps

1. Create a large top heap H[0… R]
2. Swap the heap head (maximum) with the heap tail;
3. Reduce the size of the heap by 1 to fit the top of the new array.
4. Repeat step 2 until the heap size is 1.

The demo

Code implementation

function heapSort(arr) {
  if(! arr || arr.length <2) return arr;
  Create a big top heap
  buildMaxHeap(arr);
  var size = arr.length;
  for (var i = arr.length - 1; i > 0; i--) {
    // 2. Swap the heap head (maximum) with the heap tail;
    swap(arr, 0, i);
    // 3. Reduce the size of the heap by 1, in order to adjust the top of the new array to the corresponding position;
    heapify(arr, 0, --size);
    // Repeat step 2 until the heap size is 1.
  }
  return arr;
}
/** * create a big top heap *@param {*} arr* /
function buildMaxHeap(arr) {
  for (var i = Math.floor(arr.length / 2); i >= 0; i--) {
    // Since leaf nodes do not have children, you can reduce the number of builds by eliminating the need to build the heapheapify(arr, i); }}/** * Convert a normal heap to a large root heap *@param {*} arr
 * @param {*} index
 * @param {*} size* /
function heapify(arr, index, size = arr.length) {
  var left = index * 2 + 1;
  var right = index * 2 + 2;
  var largest = index;
  if (left < size && arr[left] > arr[largest]) {
    // The left child is larger than the parent node
    largest = left;
  }
  if (right < size && arr[right] > arr[largest]) {
    // The right child is larger than the parent node
    largest = right;
  }
  if (largest !== index) {
    swap(arr, index, largest);
    heapify(arr, largest, size);
  }
}

function swap(arr, i, j) {
  var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

console.log(
  heapSort([3.5.38.15.36.26.27.2.44.46.4.19.47.48.50])
  / / [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
);
Copy the code

Count sorting

Algorithm steps

• (1) Find the largest and smallest elements in the array to be sorted
• (2) Count the number of occurrences of each element with the value of I in the array and store it into the i-th item of array C
• (3) Add all the counts (starting with the first element in C, add each term to the previous one)
• (4) Reverse fill the target array: place each element I in the C(I) item of the new array, and subtract 1 from C(I) for each element

Conditions of use

• It can only be used in scenarios where the data range is small. If the data range K is much larger than the data to be sorted n, it is not suitable for counting sort.
• Counting sort can only sort non-negative integers. Other types need to be converted to non-negative integers without changing their relative sizes.
• For example, if the test score is accurate to the last decimal place, you need to multiply all the scores by 10 to round them up.

The demo

Code implementation

function countingSort(arr) {
  if(! arr || arr.length <2) {
    return arr;
  }
  var max = Number.MIN_VALUE;
  var min = 0; // min => Can be compatible with negative numbers to achieve the purpose of capacity expansion
  for (var i = 0; i < arr.length; i++) {
    // Calculate the maximum and minimum value of the array
    max = Math.max(max, arr[i]);
    min = Math.min(min, arr[i]);
  }
  var bucket = new Array(max - min + 1).fill(0);
  for (var i = 0; i < arr.length; i++) {
    // The index of each bucket represents the value that the bucket points to in the original array. The value stored is the number of occurrences of this element
    bucket[arr[i] - min]++;
  }
  var i = 0;
  for (var j = 0; j < bucket.length; j++) {
    while (bucket[j]--) {
      Bucket [50] = 3 => newArr:[50,50,50]arr[i++] = j + min; }}return arr;
}
console.log(
  countingSort([3.5.38.15, -6.0.36.26, -27.2.44.46.4.19.47.48.50])
  / / [- 27-6, 0, 2, 3, 4, 5, 15, 19, 26, 36, 38, 44 46-48, 47, 48, 50]
);

Copy the code

Bucket sort

Algorithm steps

1. Determine the number of buckets and the data range of each bucket;
2. Put the values of the array into the appropriate bucket according to the data range;
3. Sort the data for each bucket;
4. Add the data for each bucket in turn to the array

The demo

Code implementation

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    // The current number to compare
    const current = arr[i];
    // Record the index of the number currently being compared
    let preIndex = i - 1;
    while (preIndex >= 0 && arr[preIndex] > current) {
      // When the number being compared is larger than the current number, move it back one bit
      arr[preIndex + 1] = arr[preIndex];
      preIndex--;
    }
    // The number found is no longer greater than the current number or has reached the end, insert the current number after the number being compared
    arr[preIndex + 1] = current;
  }
  return arr;
}

function bucketSort(arr, bucketSize) {
  if(! arr || arr.length <2) return arr;
  var minValue = arr[0];
  var maxValue = arr[0];
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < minValue) minValue = arr[i]; // Record the minimum value of the array
    if (arr[i] > maxValue) maxValue = arr[i]; // Record the maximum value of the array
  }
  // Initialize buckets. By default, the length of each bucket is 5
  const DEFAULT_BUCKET_SIZE = 5;
  bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
  // The number of buckets currently required
  const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
  let buckets = new Array(bucketCount);
  for (var i = 0; i < buckets.length; i++) {
    buckets[i] = [];
  }
  // Allocate data to buckets using mapping functions
  for (i = 0; i < arr.length; i++) {
    const bucketIndex = Math.floor((arr[i] - minValue) / bucketSize);
    buckets[bucketIndex].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++) {
      // Add data for each bucket in turnarr.push(buckets[i][j]); }}return arr;
}

console.log(
  bucketSort([3.5.38.15.0.36.26.2.44.46.4.19.47.48.50])
  //  [0, 2, 3, 4, 5, 15, 19, 26, 36, 38, 44, 46, 47, 48, 50]
);

Copy the code

Radix sort

Radix sort is a kind of non-comparative integer sort algorithm. Its principle is to cut the integers into different numbers according to the number of digits, and then compare them according to each number. Since integers can also represent strings (such as names or dates) and floating-point numbers in a particular format, radix sort is not restricted to integers.

Algorithm steps

Simple version of the idea:

1. Prepare an extra space, S, and find the highest digit
2. arrStarting with the units digit, stores the units digit and spaceSIndex the same number to the corresponding position
3. Use a spaceSThe rearrangementarr, so it can be in ascending order of one digit;
4. Repeat steps 2 and 3 until you reach the highest digit

The demo

Code implementation

• Simple version of the

  It’s order N^2.

  function radixSort(arr, maxDigit) {
    var mod = 10;
    var dev = 1;
    var counter = new Array(10);
    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] = [];
        }
        // Store the current number of digits in the same space index to the corresponding location such as 13 => bucket[3] = 13
        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) {
            // Follow the first-in, first-out principle
            // Reorganize the arR to achieve the ascending order of the current calculated bitsarr[pos++] = value; }}}}return arr;
  }
  /** * gets the maximum number of digits */
  function getMaxBit(arr) {
    var max = Number.MIN_SAFE_INTEGER;
    for (var i = 0; i < arr.length; i++) {
      max = Math.max(max, arr[i]);
    }
    var res = 0;
    while(max ! =0) {
      res++;
      max = Math.floor(max / 10);
    }
    return res;
  }
  const arr = [3.5.38.15.0.36.26.2.44.46.4.19.47.48.50];
  console.log(
    radixSort(arr, getMaxBit(arr))
    //  [0, 2, 3, 4, 5, 15, 19, 26, 36, 38, 44, 46, 47, 48, 50]
  );
  
  Copy the code

• Complex version

  It’s order k times N.

  /** * gets the maximum number of digits */
  function getMaxBit(arr) {
    var max = Number.MIN_SAFE_INTEGER;
    for (var i = 0; i < arr.length; i++) {
      max = Math.max(max, arr[i]);
    }
    var res = 0;
    while(max ! =0) {
      res++;
      max = Math.floor(max / 10);
    }
    return res;
  }
  
  /** * gets the digit * of a digit in a digit@param {*} x
   * @param {*} d* /
  function getDigit(x, d) {
    return (x / Math.pow(10, d - 1)) % 10;
  }
  
  function radixSort(arr) {
    if(! arr || arr.length <2) return arr;
    partition(arr, 0, arr.length - 1, getMaxBit(arr));
    return arr;
  }
  
  function partition(arr, begin, end, digit) {
    const radix = 10;
    var i = 0,
      j = 0;
  
    var bucket = new Array(end - begin + 1).fill(0);
    for (var d = 1; d <= digit; d++) {
      var count = new Array(radix).fill(0);
      for (i = begin; i <= end; i++) {
        j = getDigit(arr[i], d);
        count[j]++;
      }
      for (i = 1; i < radix; i++) {
        count[i] = count[i] + count[i - 1];
      }
      for (i = end; i >= begin; i--) {
        j = getDigit(arr[i], d);
        bucket[count[j] - 1] = arr[i];
        count[j]--;
      }
      for (i = begin, j = 0; i <= end; i++, j++) { arr[i] = bucket[j]; }}}const arr = [3.5.38.15.0.36.26.2.44.46.4.19.47.48.50];
  console.log(
    radixSort(arr)
    //  [0, 2, 3, 4, 5, 15, 19, 26, 36, 38, 44, 46, 47, 48, 50]
  );
  Copy the code

Complexity contrast

Radix sort vs counting sort vs bucket sort

There are two ways to sort radix:

• MSD sorts from the top
• LSD sorts from the low end

These three sorting algorithms all use the concept of buckets, but there are obvious differences in the way buckets are used:

• 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;