快速排序(Quick Sort)

介紹

快速排序是一種分治算法(Divide and Conquer)，它將原問題劃分為兩個子問題，一個是比基準值小的數，另一個是比基準值大的數。然後遞歸地解決這兩個子問題，最終得到排序後的結果。

(圖片來自data_structures_algorithms)

虛擬碼

運用了分治法的概念，將大的數值移到左邊，小的數值移到右邊，再遞迴運算左右兩側的數值，直到最終整個數列有序

QUICK-SORT(p, r):
    if  p < r:
        q = partition(p, r)
        QUICK-SORT(p, q - 1)
        QUICK-SORT(q + 1, r)
// when calling QUICK-SORT first time, just pass 0 and array.length - 1 as parameters

基準值（pivot）並進行數值交換，使得數列的左半部分都小於等於基準值，右半部分都大於等於基準值。最後返回基準值的位置。

partition(p, r):
    x = A[r] // 基準值pivot
    i = p - 1
    for j from p to r-1(inclusive):
        if A[j] <= x:
            i = i + 1
            exchange A[i] with A[j]
    exchange A[i + 1] with A[r]
    return i + 1

程式碼

let arr = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7];

function partition(p, r){
    let x = arr[r];
    let i = p - 1;
    for (let index = p; index <= r - 1; index++) {
        if(arr[index] <= x){
            i = i + 1;
            [arr[i], arr[index]] = [arr[index], arr[i]];
        }
    }
    [arr[i + 1], arr[r]] = [arr[r], arr[i + 1]];
    return i + 1;
}

function quickSort(p , r){
    if (p < r){
        let q = partition(p, r);
        quickSort(p, q - 1);
        quickSort(q + 1, r);
    }
}

quickSort(0, arr.length - 1)
console.log(arr) // [1, 2, 3, 4, 7, 8, 9, 10, 14, 16]

複雜度

時間複雜度

平均為:
$O(n log n)$

最壞情況每次都選到最小值當作基準值:
$O(n^2)$

空間複雜度

$O(log n)$

實戰

題目說明

912. Sort an Array

給你一個整數陣列nums，請將陣列以升序排列並返回。您必須在O(nlog(n))時間複雜度內解決此問題，並使用較小的空間複雜度。

解法

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
    return quickSort(nums)
};

function partition(nums, p, r){
    let x = nums[r];
    let i = p - 1;
    function swap(array, i, j) {
        var temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    for (let index = p; index <= r - 1; index++) {
        if(nums[index] <= x){
            i = i + 1;
            swap(nums, index, i)
        }
    }
    swap(nums, r, i + 1)
    return i + 1;
}

function quickSort(nums, p = 0 , r = nums.length - 1){
    if (p < r){
        let q = partition(nums, p, r);
        quickSort(nums, p, q - 1);
        quickSort(nums, q + 1, r);
    }
    return nums
}