Quick sort

The basic idea of quick sorting ： Separate the records to be arranged into two independent parts by one sorting , The keywords of one part of the records are smaller than those of the other part , Then the two parts of records can be sorted separately , To get the whole sequence in order .

6.1 Algorithm description

Fast sorting uses divide and conquer to put a string （list） It's divided into two strings （sub-lists）. The specific algorithm is described as follows ：

• Pick a member of the sequence , be called “ The benchmark ”（pivot）;
• Reorder the sequence , All elements smaller than the base value are placed in front of the base value , All elements that are larger than the base value are placed after the base value （ The same number can go to either side ）. After the partition exits , The benchmark is in the middle of the sequence . This is called a partition （partition） operation ;
• recursively （recursive） Sort the substrings of elements that are less than the base value and elements that are greater than the base value .

6.2 Dynamic diagram demonstration

6.3 Code implementation

function quickSort(arr, left, right) {
    var len = arr.length,
        partitionIndex,
        left = typeof left != 'number' ? 0 : left,
        right = typeof right != 'number' ? len - 1 : right;
 
    if (left < right) {
        partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex-1);
        quickSort(arr, partitionIndex+1, right);
    }
    return arr;
}
 
function partition(arr, left ,right) {     //  Partition operation 
    var pivot = left,                      //  Set reference value （pivot）
        index = pivot + 1;
    for (var i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, i, index);
            index++;
        }       
    }
    swap(arr, pivot, index - 1);
    return index-1;
}
 
function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}