快速排序（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），時間複雜度分析如下：

最差情況：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²)。
最佳&平均情況：O(n·log n)，若經分割 k =(log₂ n) 次使每段小陣列長度都變成 1，每次分割後排序 n 筆資料，共會有 (n·log₂ n) 個運算步驟，時間複雜度為 O(n·log₂ n)=O(n·log n)。