快速排序算法

快速排序（Quicksort）是對冒泡排序的一種改進。

快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

基本介紹

• 中文名：快速排序算法
• 外文名：quick sort
• 別稱：快速排序
• 提出者：C. A. R. Hoare
• 提出時間：1960年
• 套用學科：計算機科學
• 適用領域範圍：Pascal，c++等語言

算法介紹

設要排序的數組是A[0]……A[N-1]，首先任意選取一個數據（通常選用數組的第一個數）作為關鍵數據，然後將所有比它小的數都放到它左邊，所有比它大的數都放到它右邊，這個過程稱為一趟快速排序。值得注意的是，快速排序不是一種穩定的排序算法，也就是說，多個相同的值的相對位置也許會在算法結束時產生變動。

快排圖

一趟快速排序的算法是：

1）設定兩個變數i、j，排序開始的時候：i=0，j=N-1；

2）以第一個數組元素作為關鍵數據，賦值給key，即key=A[0]；

3）從j開始向前搜尋，即由後開始向前搜尋(j--)，找到第一個小於key的值A[j]，將A[j]和A[i]的值交換；

4）從i開始向後搜尋，即由前開始向後搜尋(i++)，找到第一個大於key的A[i]，將A[i]和A[j]的值交換；

5）重複第3、4步，直到i=j； (3,4步中，沒找到符合條件的值，即3中A[j]不小於key,4中A[i]不大於key的時候改變j、i的值，使得j=j-1，i=i+1，直至找到為止。找到符合條件的值，進行交換的時候i， j指針位置不變。另外，i==j這一過程一定正好是i+或j-完成的時候，此時令循環結束）。

排序演示

示例

假設用戶輸入了如下數組：

下標	0	1	2	3	4	5
數據	6	2	7	3	8	9

創建變數i=0（指向第一個數據）, j=5(指向最後一個數據), k=6(賦值為第一個數據的值)。

我們要把所有比k小的數移動到k的左面，所以我們可以開始尋找比6小的數，從j開始，從右往左找，不斷遞減變數j的值，我們找到第一個下標3的數據比6小，於是把數據3移到下標0的位置，把下標0的數據6移到下標3，完成第一次比較：

下標	0	1	2	3	4	5
數據	3	2	7	6	8	9

i=0 j=3 k=6

接著，開始第二次比較，這次要變成找比k大的了，而且要從前往後找了。遞加變數i，發現下標2的數據是第一個比k大的，於是用下標2的數據7和j指向的下標3的數據的6做交換，數據狀態變成下表：

下標	0	1	2	3	4	5
數據	3	2	6	7	8	9

i=2 j=3 k=6

稱上面兩次比較為一個循環。

接著，再遞減變數j，不斷重複進行上面的循環比較。

在本例中，我們進行一次循環，就發現i和j“碰頭”了：他們都指向了下標2。於是，第一遍比較結束。得到結果如下，凡是k(=6)左邊的數都比它小，凡是k右邊的數都比它大：

下標	0	1	2	3	4	5
數據	3	2	6	7	8	9

如果i和j沒有碰頭的話，就遞加i找大的，還沒有，就再遞減j找小的，如此反覆，不斷循環。注意判斷和尋找是同時進行的。

然後，對k兩邊的數據，再分組分別進行上述的過程，直到不能再分組為止。

注意：第一遍快速排序不會直接得到最終結果，只會把比k大和比k小的數分到k的兩邊。為了得到最後結果，需要再次對下標2兩邊的數組分別執行此步驟，然後再分解數組，直到數組不能再分解為止（只有一個數據），才能得到正確結果。

調用函式

在C語言中可以用函式qsort（）可以直接為數組進行排序。

用 法:

void qsort(void *base, int nelem, int width, int (*fcmp)(const void *,const void *));

參數：
1 待排序數組首地址
2 數組中待排序元素數量
3 各元素的占用空間大小
4 指向函式的指針，用於確定排序的順序

示例代碼

GO

// 第一種寫法func quickSort(values []int, left, right int) {    temp := values[left]    p := left    i, j := left, right    for i <= j {        for j >= p && values[j] >= temp {            j--        }        if j >= p {            values[p] = values[j]            p = j        }        for i <= p && values[i] <= temp {            i++        }        if i <= p {            values[p] = values[i]            p = i        }    }    values[p] = temp    if p-left > 1 {        quickSort(values, left, p-1)    }    if right-p > 1 {        quickSort(values, p+1, right)    }}func QuickSort(values []int) {    if len(values) <= 1 {        return    }    quickSort(values, 0, len(values)-1)}// 第二種寫法func Quick2Sort(values []int) {    if len(values) <= 1 {        return    }    mid, i := values[0], 1    head, tail := 0, len(values)-1    for head < tail {        fmt.Println(values)        if values[i] > mid {            values[i], values[tail] = values[tail], values[i]            tail--        } else {            values[i], values[head] = values[head], values[i]            head++            i++        }    }    values[head] = mid    Quick2Sort(values[:head])    Quick2Sort(values[head+1:])}// 第三種寫法func Quick3Sort(a []int,left int, right int)  {    if left >= right {        return    }    explodeIndex := left    for i := left + 1; i <= right ; i++ {        if a[left] >= a[i]{            //分割位定位++            explodeIndex ++;            a[i],a[explodeIndex] = a[explodeIndex],a[i]        }    }    //起始位和分割位    a[left], a[explodeIndex] = a[explodeIndex],a[left]    Quick3Sort(a,left,explodeIndex - 1)    Quick3Sort(a,explodeIndex + 1,right)}

Ruby

def quick_sort(a)    (x=a.pop) ? quick_sort(a.select { |i| i <= x }) + [x] + quick_sort(a.select { |i| i > x }) : []end

Erlang語言

超簡短實現：q_sort([])->[];q_sort([H|R])->q_sort([X||X<-R,X<H])++[H]++q_sort([X||X<-R,X>=H]).

Haskell語言

q_sort n=case n of    []->[]    (x:xs)->q_sort [a|a<-xs,a<=x]++[x]++q_sort [a|a<-xs,a>x]

C++語言

#include <iostream>using namespace std;void Qsort(int arr[], int low, int high){    if (high <= low) return;    int i = low;    int j = high + 1;    int key = arr[low];    while (true)    {        /*從左向右找比key大的值*/        while (arr[++i] < key)        {            if (i == high){                break;            }        }        /*從右向左找比key小的值*/        while (arr[--j] > key)        {            if (j == low){                break;            }        }        if (i >= j) break;        /*交換i,j對應的值*/        int temp = arr[i];        arr[i] = arr[j];        arr[j] = temp;    }    /*中樞值與j對應值交換*/    int temp = arr[low];    arr[low] = arr[j];    arr[j] = temp;    Qsort(arr, low, j - 1);    Qsort(arr, j + 1, high);}int main(){    int a[] = {57, 68, 59, 52, 72, 28, 96, 33, 24};    Qsort(a, 0, sizeof(a) / sizeof(a[0]) - 1);/*這裡原文第三個參數要減1否則記憶體越界*/    for(int i = 0; i < sizeof(a) / sizeof(a[0]); i++)    {        cout << a[i] << "";    }        return 0;}/*參考數據結構p274(清華大學出版社，嚴蔚敏)*/

C語言版本

void sort(int *a, int left, int right){    if(left >= right)/*如果左邊索引大於或者等於右邊的索引就代表已經整理完成一個組了*/    {        return ;    }    int i = left;    int j = right;    int key = a[left];        while(i < j)                               /*控制在當組內尋找一遍*/    {        while(i < j && key <= a[j])        /*而尋找結束的條件就是，1，找到一個小於或者大於key的數（大於或小於取決於你想升        序還是降序）2，沒有符合條件1的，並且i與j的大小沒有反轉*/         {            j--;/*向前尋找*/        }                a[i] = a[j];        /*找到一個這樣的數後就把它賦給前面的被拿走的i的值（如果第一次循環且key是        a[left]，那么就是給key）*/                while(i < j && key >= a[i])        /*這是i在當組內向前尋找，同上，不過注意與key的大小關係停止循環和上面相反，        因為排序思想是把數往兩邊扔，所以左右兩邊的數大小與key的關係相反*/        {            i++;        }                a[j] = a[i];    }        a[i] = key;/*當在當組內找完一遍以後就把中間數key回歸*/    sort(a, left, i - 1);/*最後用同樣的方式對分出來的左邊的小組進行同上的做法*/    sort(a, i + 1, right);/*用同樣的方式對分出來的右邊的小組進行同上的做法*/                       /*當然最後可能會出現很多分左右，直到每一組的i = j 為止*/}

JavaScript

const quickSort = (array) => { const sort = (arr, left = 0, right = arr.length - 1) => {  if (left >= right) {//如果左邊的索引大於等於右邊的索引說明整理完畢   return  } let i = left let j = right const baseVal = arr[j] // 取無序數組最後一個數為基準值 while (i < j) {//把所有比基準值小的數放在左邊大的數放在右邊  while (i < j && arr[i] <= baseVal) { //找到一個比基準值大的數交換   i++  }  arr[j] = arr[i] // 將較大的值放在右邊如果沒有比基準值大的數就是將自己賦值給自己（i 等於 j）  while (j > i && arr[j] >= baseVal) { //找到一個比基準值小的數交換   j-- }  arr[i] = arr[j] // 將較小的值放在左邊如果沒有找到比基準值小的數就是將自己賦值給自己（i 等於 j） } arr[j] = baseVal // 將基準值放至中央位置完成一次循環（這時候 j 等於 i ） sort(arr, left, j-1) // 將左邊的無序數組重複上面的操作 sort(arr, j+1, right) // 將右邊的無序數組重複上面的操作 } const newArr = array.concat() // 為了保證這個函式是純函式拷貝一次數組 sort(newArr) return newArr}

Java

class　Quick {    　public　void　sort(int　arr[],int　low,int　high) {        　int　l=low;        　int　h=high;        　int　povit=arr[low];                　while(l<h) {            　while(l<h&&arr[h]>=povit)            　    h--;            　if(l<h){                　arr[l]=arr[h];                　l++;            　}                        　while(l<h&&arr[l]<=povit)            　    l++;                        　if(l<h){                　arr[h]=arr[l];                　h--;            　}        　}            arr[l]=povit;        　print(arr);        　System.out.print("l="+(l+1)+"h="+(h+1)+"povit="+povit+"\n");        　if(l-1>low)sort(arr,low,l-1);        　if(h+1<high)sort(arr,h+1,high);    　}}/*//////////////////////////方式二////////////////////////////////*/更高效點的代碼：public<TextendsComparable<?superT>>T[]quickSort(T[]targetArr,intstart,intend){inti=start+1,j=end;Tkey=targetArr[start];SortUtil<T>sUtil=newSortUtil<T>();if(start=end)return(targetArr);/*從i++和j--兩個方向搜尋不滿足條件的值並交換**條件為：i++方向小於key，j--方向大於key*/while(true){while(targetArr[j].compareTo(key)>0)j--;while(targetArr[i].compareTo(key)<0&&i<j)i++;if(i>=j)break;sUtil.swap(targetArr,i,j);if(targetArr[i]==key){j--;}else{i++;}}/*關鍵數據放到‘中間’*/sUtil.swap(targetArr,start,j);if(start<i-1){this.quickSort(targetArr,start,i-1);}if(j+1<end){this.quickSort(targetArr,j+1,end);}returntargetArr;}/*//////////////方式三：減少交換次數，提高效率/////////////////////*/private<TextendsComparable<?superT>>voidquickSort(T[]targetArr,intstart,intend){inti=start,j=end;Tkey=targetArr[start];while(i<j){/*按j--方向遍歷目標數組，直到比key小的值為止*/while(j>i&&targetArr[j].compareTo(key)>=0){j--;}if(i<j){/*targetArr[i]已經保存在key中，可將後面的數填入*/targetArr[i]=targetArr[j];i++;}/*按i++方向遍歷目標數組，直到比key大的值為止*/while(i<j&&targetArr[i].compareTo(key)<=0)/*此處一定要小於等於零，假設數組之內有一億個1，0交替出現的話，而key的值又恰巧是1的話，那么這個小於等於的作用就會使下面的if語句少執行一億次。*/{i++;}if(i<j){/*targetArr[j]已保存在targetArr[i]中，可將前面的值填入*/targetArr[j]=targetArr[i];j--;}}/*此時i==j*/targetArr[i]=key;//應加判斷/*遞歸調用，把key前面的完成排序*/this.quickSort(targetArr,start,i-1);/*遞歸調用，把key後面的完成排序*/this.quickSort(targetArr,j+1,end);//兩個遞歸應加判斷}

C#

    using System;     using System.Collections.Generic;     using System.Linq;     using System.Text;    namespace test{    class QuickSort    {        static void Main(string[] args)        {            int[] array = { 49, 38, 65, 97, 76, 13, 27 };            sort(array, 0, array.Length - 1);            Console.ReadLine();        }        /**一次排序單元，完成此方法，key左邊都比key小，key右邊都比key大。         **@param array排序數組          **@param low排序起始位置          **@param high排序結束位置         **@return單元排序後的數組 */        private static int sortUnit(int[] array, int low, int high)        {            int key = array[low];            while (low < high)            {                /*從後向前搜尋比key小的值*/                while (array[high] >= key && high > low)                    --high;                 /*比key小的放左邊*/                array[low] = array[high];                   /*從前向後搜尋比key大的值，比key大的放右邊*/                while (array[low] <= key && high > low)                    ++low;                 /*比key大的放右邊*/                array[high] = array[low];            }            /*左邊都比key小，右邊都比key大。//將key放在游標當前位置。//此時low等於high */            array[low] = key;            foreach (int i in array)            {                Console.Write("{0}\t", i);            }            Console.WriteLine();            return high;        }            /**快速排序 *@paramarry *@return */        public static void sort(int[] array, int low, int high)        {            if (low >= high)                return;             /*完成一次單元排序*/            int index = sortUnit(array, low, high);             /*對左邊單元進行排序*/            sort(array, low, index - 1);            /*對右邊單元進行排序*/            sort(array, index + 1, high);        }    }} 

運行結果：27 38 13 49 76 97 65

13 27 38 49 76 97 65
13 27 38 49 65 76 97

快速排序就是遞歸調用此過程——在以49為中點分割這個數據序列，分別對前面一部分和後面一部分進行類似的快速排序，從而完成全部數據序列的快速排序，最後把此數據序列變成一個有序的序列，根據這種思想對於上述數組A的快速排序的全過程如圖6所示：

初始狀態 {49 38 65 97 76 13 27} 進行一次快速排序之後劃分為 {27 38 13} 49 {76 97 65} 分別對前後兩部分進行快速排序{27 38 13} 經第三步和第四步交換後變成 {13 27 38} 完成排序。{76 97 65} 經第三步和第四步交換後變成 {65 76 97} 完成排序。圖示

F#

let rec qsort =     function    [] -> []    |x::xs ->        qsort [for i in xs do if i < x then yield i]@        x::qsort [for i in xs do if i >= x then yield i]

PHP

<?php/** * 快速排序 * @author chaselxu */function qs($a, $s=0, $e=null) {    if($e === null) {        $e = count($a);    }    if($s >= $e) {        return $a;    }        $j = $e-1;     $i = $s;    $n = $a[$s];    //$ac = $a;    for(; $j>$i; $j--) {        if($a[$j] < $n) {            $t = $a[$i];            $a[$i] = $a[$j];            $a[$j] = $t;            for($i++;$i<$j;$i++) {                if($a[$i] > $n) {                    $t = $a[$j];                    $a[$j] = $a[$i];                    $a[$i] = $t;                    break;                }            }        }    }    //printf("\n[%s], %s ~ %s [%s] %s-%s-%s", implode($ac, ','), $s, $e, implode($a, ','), $i, $j, $e);    qs(&$a, $s, $i);    qs(&$a, $i+1, $e);    return $a;}$n = mt_rand(10000000, 99999999);$n = '7,3,2,8,7,2,0,2';//trim(preg_replace('/(\d)/', '$1,', $n), ',');$n = explode(',', $n);echo "\n".implode($n, ',');echo "\n".implode(qs($n), ',');

Pascal

這裡是完全程式，過程部分為快排program qsort;var n,p:integer;    a:array[0..100000] of integer;procedure qs(l,r:integer);//假設被排序的數組是a,且快排後按升序排列）var i,j,m,t:integer;begin  i:=l;  j:=r;//(l（left）,r（right）表示快排的左右區間)  m:=a[(l+r)div2];//注意：本句不能寫成：m:=(l+r)div2;  repeat  while a[i]<m do inc(i);  while a[j]>m do dec(j);//若是降序把'<'與‘>'互換;  if i<=j then    begin    t:=a[i];    a[i]:=a[j];    a[j]:=t;    inc(i);    dec(j);    end;  until i>j;  if l<j then qs(l,j);//遞歸查找左區間  if i<r then qs(i,r);//遞歸查找右區間end;begin  readln(n);//有n個數據要處理  for p:=1 to n do read(a[p]);//輸入數據  qs(1,n);  for p:=1 to n do write(a[p],'');//輸出快排後的數據end.或者procedure quickSort(var a:array of integer;l,r:Integer);var i,j,x:integer;begin  if l>=r then exit;  i:=l;  j:=r;  x:=a[i];  while i<=j do     begin    while (i<j)and(a[j]>x) do dec(j);    if i<j then       begin      a[i]:=a[j];      inc(i);      end;    while (i<j)and(a[i]<x) do inc(i);    if i<j then       begin      a[j]:=a[i];      dec(j);      end;    a[i]:=x;    quicksort(a,l,i-1);    quicksort(a,i+1,r);    end;end;

Python3：分而治之+遞歸

def quick_sort(data):        """快速排序"""        if len(data) >= 2:  # 遞歸入口及出口                mid = data[len(data)//2]  # 選取基準值，也可以選取第一個或最後一個元素                left, right = [], []  # 定義基準值左右兩側的列表                data.remove(mid)  # 從原始數組中移除基準值                for num in data:                        if num >= mid:                                right.append(num)                        else:                                left.append(num)                return quick_sort(left) + [mid] + quick_sort(right)        else:                return data# 示例：array = [2,3,5,7,1,4,6,15,5,2,7,9,10,15,9,17,12]print(quickSort(array))# 輸出為[1, 2, 2, 3, 4, 5, 5, 6, 7, 7, 9, 9, 10, 12, 15, 15, 17]

最佳化

三平均分區法

關於這一改進的最簡單的描述大概是這樣的：與一般的快速排序方法不同，它並不是選擇待排數組的第一個數作為中軸，而是選用待排數組最左邊、最右邊和最中間的三個元素的中間值作為中軸。這一改進對於原來的快速排序算法來說，主要有兩點優勢：
（1） 首先，它使得最壞情況發生的幾率減小了。
（2） 其次，未改進的快速排序算法為了防止比較時數組越界，在最後要設定一個哨點。

根據分區大小調整算法

這一方面的改進是針對快速排序算法的弱點進行的。快速排序對於小規模的數據集性能不是很好。可能有人認為可以忽略這個缺點不計，因為大多數排序都只要考慮大規模的適應性就行了。但是快速排序算法使用了分治技術，最終來說大的數據集都要分為小的數據集來進行處理。由此可以得到的改進就是，當數據集較小時，不必繼續遞歸調用快速排序算法，而改為調用其他的對於小規模數據集處理能力較強的排序算法來完成。Introsort就是這樣的一種算法，它開始採用快速排序算法進行排序，當遞歸達到一定深度時就改為堆排序來處理。這樣就克服了快速排序在小規模數據集處理中複雜的中軸選擇，也確保了堆排序在最壞情況下O(n log n)的複雜度。
另一種最佳化改進是當分區的規模達到一定小時，便停止快速排序算法。也即快速排序算法的最終產物是一個“幾乎”排序完成的有序數列。數列中有部分元素並沒有排到最終的有序序列的位置上，但是這種元素並不多。可以對這種“幾乎”完成排序的數列使用插入排序算法進行排序以最終完成整個排序過程。因為插入排序對於這種“幾乎”完成的排序數列有著接近線性的複雜度。這一改進被證明比持續使用快速排序算法要有效的多。
另一種快速排序的改進策略是在遞歸排序子分區的時候，總是選擇優先排序那個最小的分區。這個選擇能夠更加有效的利用存儲空間從而從整體上加速算法的執行。

不同的分區方案考慮

對於快速排序算法來說，實際上大量的時間都消耗在了分區上面，因此一個好的分區實現是非常重要的。尤其是當要分區的所有的元素值都相等時，一般的快速排序算法就陷入了最壞的一種情況，也即反覆的交換相同的元素並返回最差的中軸值。無論是任何數據集，只要它們中包含了很多相同的元素的話，這都是一個嚴重的問題，因為許多“底層”的分區都會變得完全一樣。
對於這種情況的一種改進辦法就是將分區分為三塊而不是原來的兩塊：一塊是小於中軸值的所有元素，一塊是等於中軸值的所有元素，另一塊是大於中軸值的所有元素。另一種簡單的改進方法是，當分區完成後，如果發現最左和最右兩個元素值相等的話就避免遞歸調用而採用其他的排序算法來完成。

並行的快速排序

由於快速排序算法是採用分治技術來進行實現的，這就使得它很容易能夠在多台處理機上並行處理。
在大多數情況下，創建一個執行緒所需要的時間要遠遠大於兩個元素比較和交換的時間，因此，快速排序的並行算法不可能為每個分區都創建一個新的執行緒。一般來說，會在實現代碼中設定一個閥值，如果分區的元素數目多於該閥值的話，就創建一個新的執行緒來處理這個分區的排序，否則的話就進行遞歸調用來排序。
對於這一併行快速排序算法也有其改進。該算法的主要問題在於，分區的這一步驟總是要在子序列並行處理之前完成，這就限制了整個算法的並行程度。解決方法就是將分區這一步驟也並行處理。改進後的並行快速排序算法使用2n個指針來並行處理分區這一步驟，從而增加算法的並行程度。

變種

隨機化快排

快速排序的最壞情況基於每次劃分對主元的選擇。基本的快速排序選取第一個元素作為主元。這樣在數組已經有序的情況下，每次劃分將得到最壞的結果。一種比較常見的最佳化方法是隨機化算法，即隨機選取一個元素作為主元。這種情況下雖然最壞情況仍然是O(n^2)，但最壞情況不再依賴於輸入數據，而是由於隨機函式取值不佳。實際上，隨機化快速排序得到理論最壞情況的可能性僅為1/(2^n)。所以隨機化快速排序可以對於絕大多數輸入數據達到O(nlogn)的期望時間複雜度。一位前輩做出了一個精闢的總結：“隨機化快速排序可以滿足一個人一輩子的人品需求。”

隨機化快速排序的唯一缺點在於，一旦輸入數據中有很多的相同數據，隨機化的效果將直接減弱。對於極限情況，即對於n個相同的數排序，隨機化快速排序的時間複雜度將毫無疑問的降低到O(n^2)。解決方法是用一種方法進行掃描，使沒有交換的情況下主元保留在原位置。

平衡快排

每次儘可能地選擇一個能夠代表中值的元素作為關鍵數據，然後遵循普通快排的原則進行比較、替換和遞歸。通常來說，選擇這個數據的方法是取開頭、結尾、中間3個數據，通過比較選出其中的中值。取這3個值的好處是在實際問題中，出現近似順序數據或逆序數據的機率較大，此時中間數據必然成為中值，而也是事實上的近似中值。萬一遇到正好中間大兩邊小（或反之）的數據，取的值都接近最值，那么由於至少能將兩部分分開，實際效率也會有2倍左右的增加，而且利於將數據略微打亂，破壞退化的結構。

外部快排

與普通快排不同的是，關鍵數據是一段buffer，首先將之前和之後的M/2個元素讀入buffer並對該buffer中的這些元素進行排序，然後從被排序數組的開頭（或者結尾）讀入下一個元素，假如這個元素小於buffer中最小的元素，把它寫到最開頭的空位上；假如這個元素大於buffer中最大的元素，則寫到最後的空位上；否則把buffer中最大或者最小的元素寫入數組，並把這個元素放在buffer里。保持最大值低於這些關鍵數據，最小值高於這些關鍵數據，從而避免對已經有序的中間的數據進行重排。完成後，數組的中間空位必然空出，把這個buffer寫入數組中間空位。然後遞歸地對外部更小的部分，循環地對其他部分進行排序。

三路基數快排

（Three-way Radix Quicksort，也稱作Multikey Quicksort、Multi-key Quicksort）：結合了基數排序（radix sort，如一般的字元串比較排序就是基數排序）和快排的特點，是字元串排序中比較高效的算法。該算法被排序數組的元素具有一個特點，即multikey，如一個字元串，每個字母可以看作是一個key。算法每次在被排序數組中任意選擇一個元素作為關鍵數據，首先僅考慮這個元素的第一個key（字母），然後把其他元素通過key的比較分成小於、等於、大於關鍵數據的三個部分。然後遞歸地基於這一個key位置對“小於”和“大於”部分進行排序，基於下一個key對“等於”部分進行排序。

偽代碼

非隨機

QUICKSORT(A，p，r)

1　if p<r

2　then q ←PARTITION(A，p，r)

3　QUICKSORT(A，p，q-1)

4　QUICKSORT(A，q+1，r)

為排序一個完整的數組A，最初的調用是QUICKSORT(A，1，length[A]）。

快速排序算法的關鍵是PARTITION過程，它對子數組A[p..r]進行就地重排：

PARTITION(A，p，r)

1　x←A[r]

2　i←p-1

3　for j←p to r-1

4　do if A[j]≤x

5　then i←i+1

6　exchange A[i]←→A[j]

7　exchange A[i+1]←→A[r]

8　return i+1

隨機

對PARTITION和QUICKSORT所作的改動比較小。在新的劃分過程中，我們在真正進行劃分之前實現交換：

（其中PARTITION過程同快速排序偽代碼（非隨機））

RANDOMIZED-PARTITION(A，p，r)

1　i← RANDOM(p，r)

2　exchange A[r]←→A[i]

3　return PARTITION(A，p，r)

新的快速排序過程不再調用PARTITION，而是調用RANDOMIZED-PARTITION。

RANDOMIZED-QUICKSORT(A，p，r)

1　if p<r

2　then q← RANDOMIZED-PARTITION(A，p，r)

3　RANDOMIZED-QUICKSORT(A，p，q-1)

4　RANDOMIZED-QUICKSORT(A，q+1，r)

性能分析

這裡為方便起見，我們假設算法Quick_Sort的範圍閾值為1（即一直將線性表分解到只剩一個元素），這對該算法複雜性的分析沒有本質的影響。

我們先分析函式partition的性能，該函式對於確定的輸入複雜性是確定的。觀察該函式，我們發現，對於有n個元素的確定輸入L[p..r]，該函式運行時間顯然為θ（n）。

最壞情況

無論適用哪一種方法來選擇pivot，由於我們不知道各個元素間的相對大小關係（若知道就已經排好序了），所以我們無法確定pivot的選擇對劃分造成的影響。因此對各種pivot選擇法而言，最壞情況和最好情況都是相同的。

我們從直覺上可以判斷出最壞情況發生在每次劃分過程產生的兩個區間分別包含n-1個元素和1個元素的時候（設輸入的表有n個元素）。下面我們暫時認為該猜測正確，在後文我們再詳細證明該猜測。

對於有n個元素的表L[p..r]，由於函式Partition的計算時間為θ（n），所以快速排序在序壞情況下的複雜性有遞歸式如下：

T(1)=θ(1),T(n)=T(n-1)+T(1)+θ(n) (1)

用疊代法可以解出上式的解為T(n)=θ（n²）。

這個最壞情況運行時間與插入排序是一樣的。

下面我們來證明這種每次劃分過程產生的兩個區間分別包含n-1個元素和1個元素的情況就是最壞情況。

設T(n）是過程Quick_Sort作用於規模為n的輸入上的最壞情況的時間，則

T(n)=max(T(q)+T(n-q))+θ（n)，其中1≤q≤n-1 (2)

我們假設對於任何k<n，總有T(k）≤ck，其中c為常數；顯然當k=1時是成立的。

將歸納假設代入（2），得到：

T(n）≤max(cq²+c(n-q)²)+θ（n)=c*max(q²+(n-q)²)+θ（n)

因為在[1,n-1]上q2+(n-q)2關於q遞減，所以當q=1時q²+(n-q)²有最大值n²-2(n-1）。於是有：

T(n）≤cn²-2c(n-1)+θ（n）≤cn²

只要c足夠大，上面的第二個小於等於號就可以成立。於是對於所有的n都有T(n）≤cn。

這樣，排序算法的最壞情況運行時間為θ（n²），且最壞情況發生在每次劃分過程產生的兩個區間分別包含n-1個元素和1個元素的時候。

時間複雜度為o（n²）。

最好情況

如果每次劃分過程產生的區間大小都為n/2，則快速排序法運行就快得多了。這時有：

T(n)=2T(n/2)+θ（n),T(1)=θ（1) (3)

解得：T(n)=θ（nlogn)

快速排序法最佳情況下執行過程的遞歸樹如下圖所示，圖中lgn表示以10為底的對數，而本文中用logn表示以2為底的對數.

由於快速排序法也是基於比較的排序法，其運行時間為Ω（nlogn)，所以如果每次劃分過程產生的區間大小都為n/2，則運行時間θ（nlogn）就是最好情況運行時間。

但是，是否一定要每次平均劃分才能達到最好情況呢？要理解這一點就必須理解對稱性是如何在描述運行時間的遞歸式中反映的。我們假設每次劃分過程都產生9:1的劃分，乍一看該劃分很不對稱。我們可以得到遞歸式：

T(n)=T(n/10)+T(9n/10)+θ（n),T(1)=θ（1) (4)

請注意樹的每一層都有代價n，直到在深度log10n=θ（logn）處達到邊界條件，以後各層代價至多為n。遞歸於深度log10/9n=θ（logn）處結束。這樣，快速排序的總時間代價為T(n)=θ（nlogn），從漸進意義上看就和劃分是在中間進行的一樣。事實上，即使是99:1的劃分時間代價也為θ（nlogn）。其原因在於，任何一種按常數比例進行劃分所產生的遞歸樹的深度都為θ（nlogn），其中每一層的代價為O(n），因而不管常數比例是什麼，總的運行時間都為θ（nlogn），只不過其中隱含的常數因子有所不同。（關於算法複雜性的漸進階，請參閱算法的複雜性)

平均情況

快速排序的平均運行時間為θ(nlogn)。

我們對平均情況下的性能作直覺上的分析。

要想對快速排序的平均情況有個較為清楚的概念，我們就要對遇到的各種輸入作個假設。通常都假設輸入數據的所有排列都是等可能的。後文中我們要討論這個假設。

當我們對一個隨機的輸入數組套用快速排序時，要想在每一層上都有同樣的劃分是不太可能的。我們所能期望的是某些劃分較對稱，另一些則很不對稱。事實上，我們可以證明，如果選擇L[p..r]的第一個元素作為支點元素，Partition所產生的劃分80%以上都比9:1更對稱，而另20%則比9:1差，這裡證明從略。

平均情況下，Partition產生的劃分中既有“好的”，又有“差的”。這時，與Partition執行過程對應的遞歸樹中，好、差劃分是隨機地分布在樹的各層上的。為與我們的直覺相一致，假設好、差劃分交替出現於樹的各層上，且好的劃分是最佳情況劃分，而差的劃分是最壞情況下的劃分。在根節點處，劃分的代價為n，劃分出來的兩個子表的大小為n-1和1，即最壞情況。在根的下一層，大小為n-1的子表按最佳情況劃分成大小各為（n-1)/2的兩個子表。這兒我們假設含1個元素的子表的邊界條件代價為1。

在一個差的劃分後接一個好的劃分後，產生出三個子表，大小各為1，（n-1)/2和（n-1)/2，代價共為2n-1=θ（n）。一層劃分就產生出大小為（n-1)/2+1和（n-1)/2的兩個子表，代價為n=θ（n）。這種劃分差不多是完全對稱的，比9:1的劃分要好。從直覺上看，差的劃分的代價θ（n）可被吸收到好的劃分的代價θ（n）中去，結果是一個好的劃分。這樣，當好、差劃分交替分布劃分都是好的一樣：仍是θ（nlogn），但θ記號中隱含的常數因子要略大一些。關於平均情況的嚴格分析將在後文給出。

在前文從直覺上探討快速排序的平均性態過程中，我們已假定輸入數據的所有排列都是等可能的。如果輸入的分布滿足這個假設時，快速排序是對足夠大的輸入的理想選擇。但在實際套用中，這個假設就不會總是成立。

解決的方法是，利用隨機化策略，能夠克服分布的等可能性假設所帶來的問題。

一種隨機化策略是：與對輸入的分布作“假設”不同的是對輸入的分布作“規定”。具體地說，在排序輸入的線性表前，對其元素加以隨機排列，以強制的方法使每種排列滿足等可能性。事實上，我們可以找到一個能在O(n）時間內對含n個元素的數組加以隨機排列的算法。這種修改不改變算法的最壞情況運行時間，但它卻使得運行時間能夠獨立於輸入數據已排序的情況。

另一種隨機化策略是：利用前文介紹的選擇支點元素pivot的第四種方法，即隨機地在L[p..r]中選擇一個元素作為支點元素pivot。實際套用中通常採用這種方法。

快速排序的隨機化版本有一個和其他隨機化算法一樣的有趣性質：沒有一個特別的輸入會導致最壞情況性態。這種算法的最壞情況性態是由隨機數產生器決定的。你即使有意給出一個壞的輸入也沒用，因為隨機化排列會使得輸入數據的次序對算法不產生影響。只有在隨機數產生器給出了一個很不巧的排列時，隨機化算法的最壞情況性態才會出現。事實上可以證明幾乎所有的排列都可使快速排序接近平均情況性態，只有非常少的幾個排列才會導致算法的近最壞情況性態。

一般來說，當一個算法可按多條路子做下去，但又很難決定哪一條保證是好的選擇時，隨機化策略是很有用的。如果大部分選擇都是好的，則隨機地選一個就行了。通常，一個算法在其執行過程中要做很多選擇。如果一個好的選擇的獲益大於壞的選擇的代價，那么隨機地做一個選擇就能得到一個很有效的算法。我們在前文已經了解到，對快速排序來說，一組好壞相雜的劃分仍能產生很好的運行時間。因此我們可以認為該算法的隨機化版本也能具有較好的性態。