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

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

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

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

C语言代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/* 交换记录子序列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);
    }
}