快速排序

快速排序的基本思想是：从待排序列中任取一个，作为支点。凡关键字小于支点的记录均移动至支点之前，大于支点的记录均移动至支点之后。经过一趟排序后，待排序列将分割成两个子序列，分别进行上述操作。

一趟快速排序的具体做法是：设置两个指针i和j，分别指示待排序列的左侧记录位置和右侧记录位置，首先从j所指位置开始向前查找关键字小于支点的记录，与支点交换；再从i所指位置开始向后查找关键字大于支点的记录，与支点交换，反复执行，直到i与j相等。

每次交换需要移动3次记录 (例如a和b交换，t=a;a=b;b=t)，图示中通过暂存支点的方法，以减少排序中记录的移动次数。

快速排序的时间复杂度为O(n*log2n)。待排序列越有序，排序速度越慢（可选择区间中间的记录作为支点）。快速排序是不稳定的。

C语言代码如下：

/* 交换记录子序列a[low, high]中的记录，使支点记录到位，并返回支点所在的位置 */
int Partition(int a[], int low, int high)
{
    int i=low, j=high;
    int key = a[i]; // 取第一个值作为支点
    while (i < j)    // 从表的两端交替向中间扫描
    {
        while (i<j && a[j]>=key) j--; // 从后向前，找到小于支点的记录
        a[i] = a[j];
        while (i<j && a[i]<=key) i++; // 从前向后，找到大于支点的记录
        a[j] = a[i];
    }
    a[i] = key;
    return i;   // 返回支点的位置
}
 
/* 对记录序列a[s,t]排序，注意是全闭区间 */
void QSort(int a[], int s, int t)
{
    int k;
    if (s < t)
    {
        k = Partition(a, s, t);
        QSort(a, s, k-1);
        QSort(a, k+1, t);
    }
}