排序:(四)快速排序

一、特点

Quicksort's worst-case running time is Θ(n^2) on an input array of n numbers. In spite of this slow worst-case running time, quicksort often the best practical choice for sorting beacuse it is remarkably efficient on the average: its expected running time is Θ(nlgn) and the constant factors hidden in the Θ(nlgn) notation are quite small.

Quicksort is also has the advantage of sorting in place.

快速排序的执行时间的增长率比插入排序执行时间的增长率要低。但是在小数据集上,插入排序表现要比快速排序要好。

二、算法

Quicksort, like merge sort, is based on the divide-and-conquer paradigm(分治模式). Three steps:

  1. Divide: Partition the array A[p..r] into two subarrays A[p..q-1] and A[q+1..r] such that each element of A[p..q-1] is less than or equal to A[q], which is, in turn less than or equal to each element of A[q+1..r];
  2. Conquer: sort the two subarrays A[p..q-1] and A[q+1..r] by recursive calls to quicksort;
  3. Combine: Since the subarrays are sorted in place, no needed to combine them: the entire array A[p..r] in now sorted;

三、性能

1. 时间性

性质1:快速排序最坏情况下使用大约N^2/2次比较。

性质2:快速排序平均情况下使用大约2N lgN次比较。

2. 空间性

对于一个随机文件,栈的最大规模与logN成正比,但对于退化的情况,栈的大小可能增长到与N成正比。

四、实现

#define SWAP(a, b) do{int t = a; a = b; b = t;}while(0)

static int partition(int *ary, int begin, int end)
{
    int mid_data = ary[end];
    int sp = begin;
    int p = begin;
    for (; p < end; ++p)
    {
        if (ary[p] < mid_data)
        {
            SWAP(ary[p], ary[sp]);
            sp++;
        }
    }

    SWAP(ary[end], ary[sp]);
    return sp;
}

void quicksort(int *ary, int begin, int end)
{
    int mid;
    if (begin < end)
    {
        mid = partition(ary, begin, end);
        quicksort(ary, begin, mid - 1);
        quicksort(ary, mid + 1, end);
    }
}

五、扩展

1.A randomized version of quicksort 快速排序的随机化版本

2.Hoare version of quicksort Hoare的最初版本

3.Median-of-3 partition 三数取中版本

4. 非递归快速排序

使用堆栈,每次压入待排的数组区域的指针。

发表评论