7.4 快速排序

在所研究的各种排序算法中,由 C.A.R.Hoare 提出的快速排序方法的平均时间性能是最好的。

快速排序的步骤为:

  1. 挑选基准值:从待排序的数组中选出一个元素,称为 “基准值 pivot”。
  2. 分割:重新排列数组,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(与基准值相等的数可以放到任何一边)。在这个分割结束之后,对基准值的排序就已经完成。
  3. 递归:递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

来自 Wikipedia,这里函数 quicksort 使用原地 (in-place) 分割算法的版本。

以下 quicksort 函数分别为 Wikipedia 上的伪代码版本,和 C 语言版本。

function partition(a, left, right, pivotIndex)
{
    pivotValue = a[pivotIndex]
    swap(a[pivotIndex], a[right]) // 把pivot移到结尾
    storeIndex = left
    for i from left to right-1
    {
        if a[i] <= pivotValue
        {
            swap(a[storeIndex], a[i])
            storeIndex = storeIndex + 1
        }
    }
    swap(a[right], a[storeIndex]) // 把pivot移到它最后的地方
    return storeIndex
}
#define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t))

void quicksort(element list[], int left, int right)
{
    int pivot, i, j;
    element temp;
    if (left < right) {
        i = left;
        j = right + 1;
        pivot = list[left].key;
        do {
            do
                i++;
            while (list[i].key < pivot);
            do
                j--;
            while (list[j].key > pivot);
            if (i < j)
                SWAP(list[i], list[j], temp);
        } while (i < j);
        SWAP(list[left], list[j], temp);
        quicksort(list, left, j-1);
        quicksort(list, j+1, right);
    }
}

假设输入文件包含 10 个记录,其关键字分别为 (26, 5, 37, 1, 61, 11, 59, 15, 48, 19)。下图给出了每次调用 quicksort 函数之后文件的状态。方括号用于确定尚待排序的子文件的范围。

7-1

快速排序算法在最坏情况下的时间性能是 O(n2)O(n^2)。但是在平均的情况下,基准值能够把这个序列分割成两个大小相等的子序列,它们的大小为 n/2n/2。把基准记录放置在大小为 nn 的表中的正确位置所需时间为 O(n)O(n)。如果 T(n)T(n) 表示排序具有 nn 个记录的表所需的时间,那么,对某个常量 cc 有: T(n)cn+2T(n/2),cn+2(cn/2+2T(n/4)),2cn+4T(n/4),cnlog2n+nT(1)=O(nlog2n) \begin{aligned} T(n) & \leq cn + 2T(n/2), \\ & \leq cn + 2(cn/2 + 2T(n/4)), \\ & \leq 2cn + 4T(n/4), \\ & \vdots \\ & \leq cn\log_2n + nT(1) = O(n\log_2n) \end{aligned} 这证明了快速排序的平均计算时间为 O(nlogn)O(n\log n)

算法变形

上面的快速排序总是把当前子序列的第一个记录的关键字作为基准关键字。选择基准关键字更好的方法是取当前的子序列中的第一个位置、中间位置和最后一个位置的三个关键字的中间值。因此,pivot=median{Kleft,K(left+right)/2,Kright}pivot = median\{K_{left}, K_{(left+right)/2}, K_{right}\}

results matching ""

    No results matching ""