Quick Sort 快速排序法

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

function partition(numberList, leftPointer, rightPointer) {
    var _a, _b;
    if (leftPointer === void 0) { leftPointer = 0; }
    if (rightPointer === void 0) { rightPointer = numberList.length - 1; }
    // 选择第一个元素是 pivot 数字
    var pivotNumber = numberList[leftPointer];
    // 交换资料索引起始位置
    var swapPointer = leftPointer;
    // 与 pivot 数字比较，将较小的数字放左侧，较大的数字放右侧
    for (var i = leftPointer + 1; i <= rightPointer; i++) {
        // 从第 2 个数字开始检查
        var currentCompareNumber = numberList[i];
        if (currentCompareNumber < pivotNumber) {
            // 「目前的数字」比「pivot 数字」还要小，要放在「pivot 数字」左方
            // 将「目前的数字」移动到「交换索引」位置
            swapPointer++;
            _a = [numberList[swapPointer], numberList[i]], numberList[i] = _a[0], numberList[swapPointer] = _a[1];
        }
    }
    // 将第 1 个 pivot 数字放到中间，这样可以让左侧数字是小于 pivot 数字，右侧数字大于 pivot 数字
    _b = [numberList[leftPointer], numberList[swapPointer]], numberList[swapPointer] = _b[0], numberList[leftPointer] = _b[1];
    // 回传目前 Pivot 的中心点在哪
    return swapPointer;
}
function quickSort(sortNumberList, leftPointer, rightPointer) {
    if (leftPointer === void 0) { leftPointer = 0; }
    if (rightPointer === void 0) { rightPointer = sortNumberList.length - 1; }
    // Base case is that the left and right pointers don't overlap, after which we'll be left with an array of 1 item
    if (leftPointer < rightPointer) {
        // 如果「左指标」小于「右指标」，表示还没比较完，可以继续比较
        var pivotIndex = partition(sortNumberList, leftPointer, rightPointer);
        // 对中心点左侧重新做 quick sort 排序，直到左侧所有元素都按照顺序排序
        quickSort(sortNumberList, leftPointer, pivotIndex - 1);
        // 对中心点右侧重新做 quick sort 排序，直到右侧所有元素都按照顺序排序
        quickSort(sortNumberList, pivotIndex + 1, rightPointer);
    }
    return sortNumberList;
}
var items = [5, 3, 7, 6, 2, 9, -1, 11];
console.log(quickSort(items, 0, items.length - 1));

function partition(numberList: number[], leftPointer: number = 0, rightPointer: number = numberList.length - 1) {
    // 选择第一个元素是 pivot 数字
    let pivotNumber = numberList[leftPointer];
    // 交换资料索引起始位置
    let swapPointer = leftPointer;

    // 与 pivot 数字比较，将较小的数字放左侧，较大的数字放右侧
    for (let i = leftPointer + 1; i <= rightPointer; i++) {
        // 从第 2 个数字开始检查
        let currentCompareNumber = numberList[i];
        if (currentCompareNumber < pivotNumber) {
            // 「目前的数字」比「pivot 数字」还要小，要放在「pivot 数字」左方
            // 将「目前的数字」移动到「交换索引」位置
            swapPointer++;
            [numberList[i], numberList[swapPointer]] = [numberList[swapPointer], numberList[i]];
        }
    }

    // 将第 1 个 pivot 数字放到中间，这样可以让左侧数字是小于 pivot 数字，右侧数字大于 pivot 数字
    [numberList[swapPointer], numberList[leftPointer]] = [numberList[leftPointer], numberList[swapPointer]];

    // 回传目前 Pivot 的中心点在哪
    return swapPointer;
}

function quickSort(sortNumberList: number[], leftPointer: number = 0, rightPointer: number = sortNumberList.length - 1) {
    // Base case is that the left and right pointers don't overlap, after which we'll be left with an array of 1 item
    if (leftPointer < rightPointer) {
        // 如果「左指标」小于「右指标」，表示还没比较完，可以继续比较
        let pivotIndex = partition(sortNumberList, leftPointer, rightPointer);

        // 对中心点左侧重新做 quick sort 排序，直到左侧所有元素都按照顺序排序
        quickSort(sortNumberList, leftPointer, pivotIndex - 1);

        // 对中心点右侧重新做 quick sort 排序，直到右侧所有元素都按照顺序排序
        quickSort(sortNumberList, pivotIndex + 1, rightPointer);
    }

    return sortNumberList;
}

let items = [5, 3, 7, 6, 2, 9, -1, 11];

console.log(quickSort(items, 0, items.length - 1));

// 切割数字阵列
var partitionNumberList = function(numsList:number[], leftPointer: number, rightPointer:number) {
    // 选择右指标当作「检查数字」
    let pivotCheckNumber = numsList[rightPointer];
    // 较小数字纪录指标设定为左指标
    let smallerNumberPointer = leftPointer;

    for(let i = leftPointer; i < rightPointer; i++) {
        // 从「左指标」检查到「右指标」
        if (numsList[i] <= pivotCheckNumber) {
            // 若「目前检查的数字」小于等于「检查的数字」
            // 将目前数字放到「较小数字记录指标」位置
            [numsList[smallerNumberPointer], numsList[i]] = [numsList[i], numsList[smallerNumberPointer]];
            // 「较小数字记录指标」位置往后移动
            smallerNumberPointer++;
        }
    }
    // 检查完成，确认「较小数字记录指标」数字都比「检查数字」小
    // 「较小数字记录指标」与「检查数字」交换
    //  - 「较小数字记录指标」左方都是比「检查数字」小的数字
    //  - 「较小数字记录指标」右方都是比「检查数字」大的数字
    [numsList[smallerNumberPointer], numsList[rightPointer]] = [numsList[rightPointer], numsList[smallerNumberPointer]];

    return smallerNumberPointer;
};


function quickSort(sortNumberList: number[], leftPointer: number = 0, rightPointer: number = sortNumberList.length - 1) {
    // Base case is that the left and right pointers don't overlap, after which we'll be left with an array of 1 item
    if (leftPointer < rightPointer) {
        // 如果「左指标」小于「右指标」，表示还没比较完，可以继续比较
        // 取得数字阵列 pivot 分割中心点
        let pivotIndex = partitionNumberList(sortNumberList, leftPointer, rightPointer);

        // 对中心点左侧重新做 quick sort 排序，直到左侧所有元素都按照顺序排序
        quickSort(sortNumberList, leftPointer, pivotIndex - 1);

        // 对中心点右侧重新做 quick sort 排序，直到右侧所有元素都按照顺序排序
        quickSort(sortNumberList, pivotIndex + 1, rightPointer);
    }

    return sortNumberList;
}

let items = [5, 3, 7, 6, 2, 9, -1, 11];

console.log(quickSort(items, 0, items.length - 1));