快速排序-白红宇

思路

像合并排序一样，快速排序是基于分支模式的：

分解：数组A[n]被划分两个字数组A[0..q-1]和A[q+1..n],使得对于数组A[0..q-1]中的元素都小于A[q], A[q+1..n]中的元素都大于等于A[q]。此时A[q]就得排好序。

解决：通过递归调用快速排序，对字数组A[0..q-1]和A[q+1..n]进行排序

合并：因为两个字数组已经是就地排好序的了，整个数组已经排好序了。

参考代码

按照以上模式可以写出程序：

void quickSort(int A[], int beg, int end){    if (A == NULL || beg > end)        return;    int part = getPartition(A, beg, end);    quickSort(A, beg, part-1);    quickSort(A, part+1, end);}

关键是找出划分元素的位置函数getPartition，程序如下：其中一次运行过程，如下：

int getPartition(int *a, int beg, int end){    if (beg <= end)    {        int part = beg;        for(int i = beg+1; i <= end; ++i)        {            if(a[i] <= a[beg])            {                swap(a[part+1], a[i]);                ++part;            }        }        swap(a[beg], a[part]);        return part;    }}

图示

最后，数组的最后一个元素找到了自己最终的位置上，把左右分成了两个相对独立的数组。

通过图示可以看出规律：

测试

#include 
     
      using namespace std;int getPartition(int *a, int beg, int end){    if (beg <= end)    {        int part = beg;        for(int i = beg+1; i <= end; ++i)        {            if(a[i] <= a[beg])            {                swap(a[part+1], a[i]);                ++part;            }        }        swap(a[beg], a[part]);        return part;    }}void quickSort(int *a, int beg, int end){    if (a == NULL || beg >= end)        return;    int part = getPartition(a, beg, end);    quickSort(a, beg, part-1);    quickSort(a, part+1, end);}void tranverse(int *a, int len){    for(int i = 0; i < len; ++i)    {        cout << a[i] << " ";    }    cout << endl;}int main(){    int a[] = {
   3, 9, 0, 1, 3, 2, 2, 7};    int len =  sizeof(a) / sizeof(int);    tranverse(a, len);    quickSort(a, 0, len-1);    tranverse(a, len);}

性能

时间复杂度：就平均性能而言，快速排序是目前被认为是最好的一种内部排序方法。通常认为快速排序在平均情况下的时间复杂度为O(nlogn)。若初始记录序列按关键字有序或基本有序，快速排序将蜕化为冒泡排序，其时间复杂度为O(n²)。

空间复杂度：最坏情况下，若每趟排序之后，枢轴位置均偏向子序列的一端（有序），栈的最大深度为n。如果在一趟划分之后比较分割所得两部分的长度，且先对长度短的子序列中的记录进行快速排序，则栈的最大深度可降为O(logn)。

性能改善：在区间选取随机数，把该数放在应在的位置，可以有效避免最坏情况。如下

RANDOMIZED-PARTITION(A,p,r)   i = RANDOM(p,r)   exchange A[r] <->A[j]   return PARTITION(A,p,r)

稳定性

不稳定

本文转自jihite博客园博客，原文链接：http://www.cnblogs.com/kaituorensheng/archive/2013/02/23/2923771.html，如需转载请自行联系原作者