快速排序(Quick Sort)


快速排序(quick sort)

以「分治法(divide and conquer)」實現,使用「分區(partition)」概念輔助,每次排序後分為兩區,一區比參考值小、另一區比參考值大,兩區資料個數不一定相同,且僅參考值本身被排在正確位置上。

圖示

現假設有一陣列 [6,5,9,4,1],要透過快速排序將陣列由小排到大的過程如下,綠底者代表當前參考值 x,也就是「基準(pivot)」;j 走過的每一項都會與其比較,若 arr[j]<=x,就會將第 (i+1) 項與第 j 項互換,待每筆資料都比較過後,到第 i 項為止的值都比 x 小,再將當時的第 (i+1) 項與 x 互換,使 x 抵達正確位置:

值得注意的是,雖然 5 跟 9 並沒有被當「x」與其他值比較、並找到正確排序位置,但在其他三筆資料完成排序後,5 跟 9 也都已經抵達正確位置,因此這兩筆資料的排序過程可忽略。

偽代碼&說明

「快速排序」的偽代碼分為兩個部分,先在第一部分的「PARTITION()」找到「pivot」的正確位置後,再用第二部分的「QUICK-SORT()」實現「分而治之」,將「pivot」兩端的值各自排序,直到所有的值當過「pivot」被放到正確位置上、或不用當「pivot」就抵達正確位置為止。

下列偽代碼及程式碼皆以「將陣列由小到大排序」為目標:

在把其他值分別放到「pivot」的左右兩側時,與「pivot」大小相等的值可能全被放到左邊、也可能全被放到右邊,兩種情況都不會照既有的順序排列,因此快速排序為「不穩定排序(unstable sort)」。

例如下圖中,若以綠色的 5 為「pivot」,經過快速排序後,剩下的 5 可能全被移到綠色 5 的左邊、也可能全被移到綠色 5 的右邊,但不論是何種情況,這四個 5 都已經不會按照原本的紅、綠、橙、黃順序排列:

快速排序為「不穩定排序」


程式碼範例(JavaScript)

//第一部分
function partition(p,r){
    let x = arr[r];                      //陣列的最後一項設為跟其他值比較的pivot
    let i = p-1;                         //標示最後一個比pivot小的值所在位置 
    for(let j=p; j<=(r-1); j++){         //讓j從頭開始跑
        if(arr[j] <= x){                 //只要有任何值比pivot小,就將其往前放
            i += 1;
            let temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    let temp = arr[i+1];                 //將pivot放到第(i+1)項,從頭到第i項都比pivot小、從第(i+2)項到尾都比pivot大
    arr[i+1] = arr[r];
    arr[r] = temp;
    return i+1;                          //回傳到quickSort()成為下一輪運算的q
}

//第二部分
function quickSort(p,r){                 //第一次輸入時,p為0、r為arr.length-1
    if(p<r){
        let q = partition(p,r);          //透過partition()找到q的正確位置
        quickSort(p, q-1);               //透過遞迴排序所有比q小的值
        quickSort(q+1, r);               //透過遞迴排序所有比q大的值
    }
}

時間複雜度

現假設陣列中共有 (n+1) 筆資料(索引值從 0 到 n),時間複雜度分析如下:

  1. 最差情況:O(n²),所有的值都要做一次「PARTITION()」抵達正確位置,因此最末項要移動 n 次、次末項要移動 (n-1) 次...第 1 項要移動 1 次、第 0 項移動 0 次,全部共移動 [n+(n-1)+…+1+0] = [(n+0)‧(n+1)]/2 = (n²+n)/2 次,O((n²+n)/2)=O(n²)。
  2. 最佳&平均情況:O(n·log n),若經分割 k =(log₂ n) 次使每段小陣列長度都變成 1,每次分割後排序 n 筆資料,共會有 (n·log₂ n) 個運算步驟,時間複雜度為 O(n·log₂ n)=O(n·log n)。


空間複雜度

  1. 最差情況:O(n),若未限制巢狀遞迴過程使用空間的上界,將達 O(n)。
  2. 平均&最佳情況:O(log n):若為「原地演算法(in-place algorithm)」版本的快速排序,可透過最佳化,使空間複雜度優化為 O(log n)。

參考資料

  1. 快速排序(QuickSort)的稳定性分析
  2. 快速排序 Quicksort
#演算法 #快速排序







你可能感興趣的文章

Facebook粉絲頁分析三部曲-爬取,分析,預測

Facebook粉絲頁分析三部曲-爬取,分析,預測

JavaScript 學習筆記 - Function

JavaScript 學習筆記 - Function

[Linux] wsl系統遷移

[Linux] wsl系統遷移






留言討論