快速排序

快速排序的一般写法。下面的写法是双指针双向而行。区分交汇点左侧的值和右侧的值。

void QuickSort(int R[], int lo, int hi){
    int i = lo, j = hi;
    int temp;
    if(i < j){
        temp = R[i];
        while (i != j)
        {
            while(j > i && R[j] > temp)-- j;
            R[i] = R[j];
            while(i < j && R[i] < temp)++ i;
            R[j] = R[i];
        }
        R[i] = temp;
        QuickSort(R, lo, i - 1);
        QuickSort(R, i + 1, hi);
    }
}

在取前面的最小的 k 个数的算法题中，可以在快排基础上做优化。

/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number[]}
 */
var getLeastNumbers = function(arr, k) {
    if (k === 0) {
        return [];
    }
    if (arr.length <= k) {
        return arr;
    }

    quickSort(arr, 0, arr.length-1, k-1);

    return arr.slice(0, k);
};

function quickSort(arr, left, right, target) {
    const mid = partition(arr, left, right);

    if (mid === target) {
        return;
    }
    mid > target ? quickSort(arr, left, mid-1, target) : quickSort(arr, mid+1, right, target);
}

function partition(arr, left, right) {
    const flag = arr[right];
    let i = left-1;
    for (let j = left; j < right; j++) {
        if (arr[j] <= flag) {
            swap(arr, ++i, j);
        }
    }
    swap(arr, ++i, right);
    return i;
}

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

这里的 partition 和前面不同，使用的双指针是同向而行的，碰到较小值就交换位置。

function partition(arr, left, right) {
    const flag = arr[right];
    let i = left-1;
    for (let j = left; j < right; j++) {
        if (arr[j] <= flag) {
            swap(arr, ++i, j);
        }
    }
    swap(arr, ++i, right);
    return i;
}

针对前 k 个数做优化。如果前 k 个数排好就返回。如果排序左侧范围太大就缩小范围，如果左侧范围太小就排序剩余部分。

function quickSort(arr, left, right, target) {
    const mid = partition(arr, left, right);

    if (mid === target) {
        return;
    }
    mid > target ? quickSort(arr, left, mid-1, target) : quickSort(arr, mid+1, right, target);
}