QuickSort

快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分为两个子序列（sub-lists）。
步骤：
1.从队列中挑出一个元素，称为“基准”（pivot）。

2.重新排序數列，所有元素比基准值小的放在基准前面，所有元素比值基准大的放在基准的後面（相同的數可以到任一边）。
在这个分割结束之后，該基准就位于数列的中间位置。

3.递归地（recursive）把小于基准的元素子队列和大于基准的元素的子队列排序。

在平均狀況下，排序n個項目要Ο(n$\log{n}$)次比較。在最坏情况下需要Ο($n^2$)次比較。
事实上，快速排序通常明显比其他Ο(n$\log{n}$)算法更快，因為它的內部循环（inner
loop）可以在大部分的架构上很有效率地被实现出來。

代码 1：

void quick_sort(char array[], int left, int right)
{

    int i, j;
    char pivot;

    if (left < right){
        i = left, j = right+1;
        pivot = array[left];
        while (i < j){
            while (pivot > array[++i]){
            }

            while (pivot < array[--j]){
            }

            if (i < j){
                swap(&array[i], &array[j]);
            }
        }

        swap(&array[left], &array[j]);
        quick_sort(array, left, j-1);
        quick_sort(array, j+1, right);
    }
    return;
}

快速排序的最坏情况

在最壞狀況下則需要Ο($n^2$)比较。
最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。
因此，快速排序必须做n-1次划分，第i次划分开始时区间长度为n-i+1，所需的比较次数为n-i(1≤i≤n-1)，故总的比较次数达到最大值：

Cmax = n(n-1)/2=O($n^2$)

如果按上面给出的划分算法，每次取当前无序区的第1个记录为基准，那么当文件的记录已按递增序(或递减序)排列时，每次划分所取的基准就是当前无序区中关键字最小(或最大)的记录，则快速排序所需的比较次数反而最多。
基准的选择影响了算法的性能。

基准的选择

在当前无序区中选取划分的基准关键字是决定算法性能的关键。

三者取中规则

在当前区间里，将该区间首、尾和中间位置上的关键字比较，取三者之中值所对应的记录作为基准，在划分开始前将该基准记录和该区伺的第1个记录进行交换，此后的划分过程与上面所给的quick_sort算法完全相同。

代码：

char Median3(char A[], int left, int right )
{
    int center = (left + right) / 2;
    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] );
    /* A[left] <= A[center] <= A[right] */
    swap(&A[center], &A[left]); /* 将pivot藏到右边 */
    return A[left]; /* 返回 pivot */
}

取随机数k(left≤k≤right)作为基准

选取基准最好的方法是用一个随机函数产生一个取位于left和right之间的随机数k(left≤k≤right)，用R[k]作为基准，这相当于强迫R[left..right]中的记录是随机分布的。用此方法所得到的快速排序一般称为随机的快速排序。

代码：

int get_random(char A[], int left,int right)
{
    // 产生 left 和 right 之间的一个随机整数
    int result = left + rand()%(right - left + 1);
    swap(&A[result], &A[left]); /* 将pivot藏到左边 */
    return A[left]; /* 返回 pivot */
}

完整代码：
https://github.com/don7hao/algorithm/blob/master/sort/quick_sort.c