快速排序

思想

快速排序（quick sort）由C. A. R. Hoare在1962年提出。它的基本思想是：選擇一個基准數（樞紐元），通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都小於或等於基准數，另外一部分的所有數據都要大於或等於基准數，然後再按此方法對這兩部分數據分別進行快速排序。

將數組 S 排序的基本算法由下列四步組成

1. 如果 S 中元素個數是 0 或 1，則返回
2. 取 S 中一元素 v，稱之為樞紐元（pivot）
3. 將S - {v}分成兩個不相交集合：S1中的元素都小於或等於v，S2中的元素都大於或等於v
4. 返回 { quickSort(S1) 後，繼隨 v，繼而 quickSort(S2) }

樞紐元的選取

錯誤的做法

通常的、沒有經過充分考慮的選擇是將第一個元素或最後一個元素用作樞紐元。如果輸入是隨機的，那麼這是可以接受的。但是如果輸入是預排序的或是反序的，那麼這樣的樞紐元就產生一個劣質的分割，因為所有的元素不是都被劃入了 S1 就是被劃入了 S2。實際上，如果第一個元素用作樞紐元而且輸入是預先排序的，那麼快速排序花費的時間將是二次的。

pivot = A[right];

安全的做法

一種安全的做法是隨機選取樞紐元。一般來說這種策略非常安全，因為隨機的樞紐元不可能總在接連不斷地產生劣質的分割。另一方面，隨機數的生成一般代價昂貴，根本減少不了算法其余部分的平均運行時間。

pivot = Random(left, right);
exchange A[right] with pivot

三數中值分割法（Median-of-Three Partitioning）

一組 N 個數的中值是第 ⌈ N / 2⌉ 個最大的數。樞紐元的最好的選擇是數組的中值。一般的做法是使用左端、右端和中心位置上的三個元素的中值作為樞紐元。下述函數將樞紐與置於最右邊第二個位置。由於最左邊的元素小於樞紐元、最右邊的元素大於樞紐元，使得雙向分割時i、j不會超出邊界。

ElementType Median3(ElementType a[], int left, int right)
{
    int center = (left + right) / 2;
 
    //sort a[left], a[center] and a[right]
    if (a[left] > a[center])
        Swap(&a[left], &a[center]);
    if (a[left] > a[right])
        Swap(&a[left], &a[right]);
    if (a[center] > a[right])
        Swap(&a[center], &a[right]);
 
    Swap(&a[center], &a[right - 1]);     //hide pivot
    return a[right - 1];                 //return pivot
}

分割策略

在分割階段要做的就是把所有小元素移到數組的左邊而把所有大元素移到數組的右邊。調用該算法前應該使用好的策略選取樞紐元，並將其與最右邊的元素交換（單向分割）或倒數第二個元素交換（雙向分割），使其離開要被分割的區域： A[left] 到 A[right - 1] 或 A[left] 到 A[right - 2]。

單向分割

Partition(A, left, right)
 
    pivot = A[right]        //樞紐元位於最右邊
    i = left - 1
    for j = left to right - 1
        if(A[j] <= pivot)                                                     
            i++
            if(i != j )
                exchange A[i] with A[j]
    exchange A[i + 1] with A[right]
    return i + 1

雙向分割

pivot = Median3(a, left, right);        //使用三數中值分割法獲取樞紐元
i = left;j = right - 1;
for (; ; )
{
    while (a[++i] < pivot) {}
    while (a[--j] > pivot) {}
    if (i < j)
        Swap(&a[i], &a[j]);
    else
        break;
}
Swap(&a[i], &a[right - 1]);           //restore pivot

算法主體

算法中的CUTOFF用於分辨排序的規模，因為當排序規模過小時宜采用直接插入排序。

#define CUTOFF 3
void QuickSort(ElementType a[], int left, int right)
{
    int i, j;
    ElementType pivot;
 
    if (left + CUTOFF <= right)
    {
        pivot = Median3(a, left, right);
        i = left; j = right - 1;
        for (; ; )
        {
            while (a[++i] < pivot) {}
            while (a[--j] > pivot) {}
            if (i < j)
                Swap(&a[i], &a[j]);
            else
                break;
        }
        Swap(&a[i], &a[right - 1]);      //把樞紐元的位置恢復為兩個集合的中間
 
        QuickSort(a, left, i - 1);
        QuickSort(a, i + 1, right);
    }
    else
        InsertionSort(a + left, right - left + 1);
}