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));