The basic idea of quicksort

function MySort( arr ) {
    // Swap functions
    const swap = (x, y) = > {
        let temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }
    // Split the array to find the reference point
    const partition = (left, right) = > {
        let len = right - left + 1;
        if(len <= 1) return;
        let first = arr[left];
        while(left < right){
            while(left < right && arr[right] >= first) --right;
            swap(left, right);
            while(left < right && arr[left] <= first) ++left;
            swap(left, right);
        }
        return left
    }
 
    const quickSort = (left, right) = > {
        if(right - left <= 0) return;
        const point = partition(left, right);
        // Recursive call to quicksort the left subtree group
        quickSort(left, point-1);
        // A recursive call to quicksort the right subtree group
        quickSort(point+1, right);
    }
    quickSort(0, arr.length-1);
    return arr;
}
Copy the code

Arr [right] >= first; arr[left] <= first; arr[left] <= first; Then first find the reference point, find the reference point point, judge the position of the reference point,

  1. If the position is exactly zeroK-1This means that this number is the KTH largest number, because everything to the left of the reference point is larger than it, and the array starts at 0 and returns that number
  2. If the position is less thanK-1If the number you are looking for is to the right of the reference point, then you just need to fast-sort the array on the right
  3. If the position is greater thanK-1If the number you are looking for is to the left of the reference point, then you only need to fast-sort the data to the left of the reference point in the array

The special case is if there’s only one element in the array, you don’t need to sort it, you just return it

function quickSort(left, right){
    if(right - left <= 0) return a[left];
    let partitionIndex = partition(left, right);
    if(partitionIndex === K - 1) return a[partitionIndex];
    if(partitionIndex < K-1) return quickSort(partitionIndex+1, right);
    return quickSort(left, partitionIndex - 1);
}

Copy the code