Quicksort- Tony Hoare - 1962

和merge-sort一樣，他使用了Divide and conquer的想法，下面是對於一個陣列進行快速排序的三步分治過程

• Divide : 在陣列中找到一個元素，把這個元素作為基準點，將陣列拆分成兩個子陣列，中每一個元素皆小於等於，中每一個元素皆大於等於。
• Conquer : 通過遞迴呼叫Quicksort，對和進行排序。
• Combine : 因為子陣列都是在原陣列中進行排序，就如同插入排序法一樣，所以不需要合併。

QUICKSORT(A, low ,high)
    if low < high
        q = PARTITION(A, low, high)
        QUICKSORT(A, low, q-1)
        QUICKSORT(A, q+1, high)

為了排序A陣列中所有元素，一開始呼叫QUICKSORT(A, 1, A.lenght)

接著開始拆分陣列，這也是Quicksort的關鍵步驟

PARTITION(A, low, high)
    pivot = A[high]
    i = low - 1
    for j = low to high - 1
        if A[j] <= pivot
            i = i + 1
            exchange A[i] with A[j]
    exchangeA[i + 1] with A[high]
    return i + 1

選取一個pivot，也就是基準點，以他為基準進行陣列的拆分，程式進行的過程中會將陣列拆分成四個部分，每一個部分都會滿足一定的性質，如小於等於pivot等等...，這樣的性質可以做為循環不變量使用。

整個Quicksort的概念，以A = {6 10 13 5 8 3 2 11}作為舉例

6 10 13 5 8 3 2 11, 選取6作為pivot
^  ^
i  j        ,j開始往後走，直到找到元素小於pivot, 找到時, 進行交換
------------------------------------------------------
6 10 13 5 8 3 2 11
  ^     ^
  i     j  ,i = i + 1
------------------------------------------------------
6 5 13 10 8 3 2 11
  ^     ^
  i     j  ,交換
------------------------------------------------------
6 5 3 10 8 13 2 11
    ^         ^
    i         j
------------------------------------------------------
6 5 3 2 8 13 10 11
      ^           ^
      i           j->
------------------------------------------------------
6 5 3 2 8 13 10 11
^     ^
pivot i     ,最後, pivot和i指到的元素進行交換，也就是將pivot移到中間
------------------------------------------------------
2 5 3 6 8 13 10 11
      ^
    pivot
我們會發現pivot左邊都比他小，右邊都比他大

整個程式大約會將陣列劃分成4個部分，如下圖

會劃分成比pivot小的，比pivot大的，pivot本身，若r不等於陣列最後的index，則會有一個部分是和pivot無關的，這個例子中只有三個部分。

C++進行實作

#include <iostream>

using namespace std;
void quick_sort(int *, int, int);
int partition(int *, int, int);
int main(void)
{
    int A[10] = {2, 7, 3, 6, 1, 9, 0, 4, 7, 3};
    quick_sort(A, 0, 9);
    for (auto i : A)
    {
        cout << i << ' ';
    }
}

void quick_sort(int *a, int low, int high)
{
    if (low < high)
    {
        int q = partition(a, low, high);
        quick_sort(a, low, q - 1);
        quick_sort(a, q + 1, high);
    }
}

int partition(int *a, int low, int high)
{
    int pivot = a[high];
    int i = low - 1;
    for (int j = low; j <= high - 1; j++)
    {
        if (a[j] <= pivot)
        {
            i = i + 1;
            swap(a[i], a[j]);
        }
    }
    swap(a[i + 1], a[high]);
    return i + 1;
}

Quicksort效率

Quicksort的執行時間取決於在劃分陣列時是否平衡，而平衡與否取決於劃分的元素。如果劃分時是平衡的，那Quicksort看起來會像是merge-sort一樣，且有一樣的效率。如果劃分的不平衡，則會十分接近插入排序。

最壞情況

如果無法正常的劃分陣列，則Quicksort的效率會十分的低落，如果我們選取的pivot都比其他的數來的大或是小，便無法把陣列平衡的劃分了，而這樣的情況會發生在整個陣列已經排序完畢，或是整個陣列是逆序排列的。也就是當兩個子陣列分別一個出現n - 1個元素，另一個陣列出現0個元素時。
劃分陣列的操作大概需要。由於對一個大小為0的陣列進行遞迴呼叫會直接回傳，因此，因此整個時間複雜度可以表示成下面

，使用主方法後，得到結果為，而插入排序法最壞的情況也是，因此，在最壞的情況下，Quicksort的執行效率不比插入排序法來的好。但是對於已經排序好的陣列來說，Quicksort複雜度仍然是，此時插入排序法的時間複雜度為，效率比Quicksort來的好。

總共有n個，每一個執行時間為，因此n個時間複雜度為，整個為

最好情況

Quicksort的平均情況接近於其最好情況，而非其最差情況。假設我們在劃分陣列的時候兩邊元素的大小為9:1的形式，我們試著將在個情況下，Quicksort的遞迴式寫出


我們將遞迴樹畫出，會發現左子樹和右子樹的高度不同，每一層我們將其加總，第一層n需要，第二層，同樣需要，直到深度達到以後，每一層所需要的時間就會小於等於，因為右子樹已經停止展開了，因此該層的加總不會到。

我們將每一層所需要的時間進行加總，得到，加上所有葉子所需要的時間，得到，這個不等式的上界為，下界為，因此可以表示成，也可以表示成。(如果要求嚴謹必須使用代換法進行證明)

我們在來看到如果我們進行Quicksort，剛好遇到恰好將陣列劃分成兩個區塊的情況，可以表示成，使用主定理得到結果為。

到這裡證明完一件事情，即便陣列拆分的極度不平衡，他們的效率是一樣好的，都是。

平均情況

對於Quicksort來說，他的行為取決維陣列中每一個元素的相對位置，而不是元素本身，因此，我們需要對輸入各種情況的頻率做出假設。

假設我們一開始是幸運的，剛好將陣列1:1劃分，接著出現不幸運的情況，將陣列9:1劃分，接著又出現幸運的情況，我們試著分析這樣的情況。假設幸運的情況為，不幸運為

我們可以列出下面的式子，每一次幸運之後會接著不幸運，不幸運後會接著幸運

使用代換法求解:
解，將代換掉，先將帶入，得到
，再將其代回，得到

(使用主定理)

這個情況下，總體來說，我們是幸運的

這張圖表示先出現不幸運的劃分，再出現幸運的劃分，待解決的為和，也就是灰色矩形的部分

這張圖表示一開始就出現幸運的劃分，待解決的問題同樣是兩個灰色矩形的部分

這裡有一個問題，我們的幸運只考慮陣列劃分的方式，而沒有考慮陣列中元素排序的方式，如果陣列中的元素是已經排序完成的或逆序的，時間複雜度為，為了確保我們是幸運的，這裡有兩個做法，第一個為隨機排序陣列中的元素，另一種是隨機選取基準點。

隨機化Quicksort

在討論隨機化Quicksort的平均情況之前，會先假設輸入的數據的所有種組合的機率都是相等的(實際上不會如此)，這麼做的好處，就是我們不用考慮輸入陣列元素的順序，不論輸入什麼元素，屆時都將是隨機排序的，而因為Quicksort不會受到元素大小影響，因此元素的數值我們也不用在意了。不同於原本的Quicksort，在已經排序的情況下效率低落。也因此我們不需要對輸入的陣列中元素的分佈有任何假設，像是確定沒有完成排序等等。沒有任何一種輸入是確定會發生最差的執行效率，會產生出最差執行效率的情況取決於隨機數的產生。

現在最差的情況不由輸入決定，而是取決於隨機數產生器，數學上可以去計算出出現最差情況的邊界，得到出現的可能性，為了方便分析，使用隨機選取基準點(pivot)的方式進行隨機化，不同於普通Quicksort每次選取作為基準點，我們使用的隨機抽樣為在中隨機選取一個元素作為基準點。

達到這一件事情，實踐的方式是將和中隨機選取的元素進行交換。這模做可以確保基準點pivot = 是機率均等的從陣列個元素中隨機選取的(這樣隨機選擇也有可能選取到自己)。

RANDOMIZED-PARTITION(A, low ,high)
    i = RANDOM(p, r)
    exchange A[high] with A[i]
    return PARTITION(A, low, high)

RANDOMIZED-QUICKSORT(A, low, high)
if low < high
    q = RANDOMIZED-PARTITION(A, low, high)
    RANDOMIZED-QUICKSORT(A, low, high - 1)
    RANDOMIZED-QUICKSORT(A, q+1, high)

參考資料:Introduction to algorithms 3rd