思想
快速排序(quick sort)由C. A. R. Hoare在1962年提出。它的基本思想是：選擇一個基準數(樞紐元)，通過一趟排序将要排序的資料分割成獨立的兩部分，其中一部分的所有資料都小于或等于基準數，另外一部分的所有資料都要大于或等于基準數，然後再按此方法對這兩部分資料分别進行快速排序。
将數組 S 排序的基本算法由下列四步組成
如果 S 中元素個數是 0 或 1，則傳回
取 S 中一進制素 v，稱之為樞紐元(pivot)
将S - {v}分成兩個不相交集合：S1中的元素都小于或等于v，S2中的元素都大于或等于v
傳回 { 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[],intleft,intright){
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
voidQuickSort(ElementType a[],intleft,intright){
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);
}
