The basic idea of quicksort is that the records to be sorted are separated into two independent parts through a sort. If the keywords of one part of the records are smaller than those of the other part, the two parts of the records can be sorted separately to achieve the order of the whole sequence.

Algorithm is introduced

Quick Sort uses a divide-and-conquer strategy. Its basic idea is: select a benchmark number, and divide the sorted data into two independent parts through a sorting; All of the numbers in one part are smaller than all of the numbers in the other part. Then, this method is used to sort the two parts of data, and the whole sorting process can be carried out recursively, so as to achieve the whole data into an ordered sequence.

Algorithm description:

Quicksort uses divide-and-conquer to divide a list into two sub-lists. The specific algorithm is described as follows:

  • Pick an element from the sequence, called pivot,
  • Reorder the array so that all elements smaller than the base value are placed in front of the base value and all elements larger than the base value are placed behind the base value (the same number can go to either side). After the partition exits, the benchmark is in the middle of the array. This is called a partition operation.
  • Recursively sorts subsequences of elements less than a reference and subsequences of elements greater than a reference.

Dynamic graph demonstration

Note: The reference values are based on array subscripts.

Code implementation

Var quickSort = function(arr) {if (arr. Length <= 1) {return arr; } var pivotIndex = math.floor (arr.length / 2); Var pivot = pivot. Splice (pivotIndex, 1)[0]; Var left = []; Var right = []; for (var i = 0; i < arr.length; I ++){if (arr[I] < pivot) {left.push(arr[I]); } else {right. Push (arr [I]); }} return quickSort(left). Concat ([pivot], quickSort(right)); };Copy the code

Select the base for reference, divide the array, divide and conquer, for novice to understand the core idea of quick row “reference – partition – recursion”, it is easy to understand.

Both the implementation of the sort, and in line with the idea of quick sort, why will be criticized? It turns out that:

  1. The cardinality is taken by the splice() function instead of the subscript used in algorithms. Cardinality is only a reference object, as long as it can be obtained from the array when comparing, so it only needs to know its index, calling the function to delete the cardinality will only be more time-consuming;

  2. When partitioning by cardinality, two arrays are generated for storage, which takes up more storage space (increasing space complexity).

Faster sorting

Implementation idea:

  1. Take the 0th number of the sorting interval as the radix by the following table
  2. After sorting the cardinality of the interval, we go from right to left, looking for something smaller than the cardinality, and from left to right, looking for something larger than the cardinality, and we switch places;
  3. Repeat step 2 until I >= j;
  4. The cardinal number and the element with subscript I are exchanged in place to achieve partition;
  5. The number to the left of the recursive sort cardinality, the number to the right of the recursive sort cardinality, returns an array.

Code implementation

var quickSort_New = function(ary, left, right) { if(left >= right) { return ary; } var i = left, j = right; base = ary[left]; While (I <j &ary [j] >= base) {j--; while (I <j &ary [j] >= base) {j--; While (I <j &&ary [I] <= base) {I ++} if (I <j) {var temp = ary[I]; ary[i] = ary[j]; ary[j] = temp; } } ary[left] = ary[i]; ary[i] = base; quickSort_New(ary, left, i-1); quickSort_New(ary, i+1, right); return ary; }Copy the code

Note: The above way to use two-way recursive fast search to achieve the efficiency of double.

DORA sister [ITI2018] front-end fishing technology group

Welcome everyone technical exchange push touch fish help all can – link

Series of links (will be updated later)

  • Insertion Sort

  • The difference between bubble sort and selection sort