快速排序


思想

快速排序（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);
}

本文永久更新链接地址：

相关内容