排序算法——快速排序

参考书籍:《数据结构与算法分析——C语言描述》

快速排序是在实践中最快的已知排序算法,它的平均时间复杂度O(NlogN)。当然在最坏的情况下为O(N^2),但稍加努力就可以避免这种情形。

像归并排序一样,快速排序也是一种分治的递归算法,可简单表示如下:

技术分享

将数组S排序的基本算法由下列简单的四步组成。

1、数组元素至少大于或等于4个,否则直接利用插入排序完成。

2、利用特定方法(三数中值分割法)取数组某一特定元素V,称之为枢纽元。

3、将数组中其他元素(即S-{V})分成两个不相交的子集。S1={x∈S-{V} | x≤V}和S2={x∈S-{V} | x≥V}。

4、继而对两个子集S1和S2进行同理1-3的递归运算。


如何选取枢纽元呢?

此处我们介绍是三数中值分割法。选取数组中最左端、最右端和中心位置的三个元素,比较三个元素的大小,并按照小的在左边交换彼此位置,取中间值作为枢纽元。

例如:

对于初始序列:

技术分享

left=8;right=0;center=6。

显然此处枢纽元应为piovt=6;并且此时的排序为:

技术分享

然后我们选取两个指示器i和j。从序列的首尾两端出发,除枢纽元外的元素与枢纽元进行比较。此时可把枢纽元6移至right-1的位置(因为right已经比piovt大了,left已经比piovt小了)。

即:

技术分享

如果i指示的数比枢纽元小,则i++;直至遇到大于等于枢纽元的数停止。

如果j指示的数比枢纽元大,则j++;直至遇到小于等于枢纽元的数停止。

若此时i<j(说明元素没有全部比完),则交换i和j位置的数。继续上述的比较,直至i≥j(说明元素全部比完)。

比完时序列如下:

技术分享

此时在交换位置i的数和枢纽元。如下图所示:

技术分享

枢纽元已将原序列分割为两个子集:

1、大于枢纽元:7,9,8

2、小于枢纽元:0,1,4,2,3,5

同理可以将两个子集继续进行如此的分割排序。

代码实现:

#include<stdio.h>

void QuickSort(int *data,int n);
void Qsort(int *data,int left,int right);
int Median3(int *data,int left,int right);//3数中值分割法取出枢纽元
void Swap(int *a,int *b);
void InsertSort(int *data,int N);

int main()
{
    int i=0;
    int data[8]={34,8,64,51,32,21,9,5};

    printf("Before Sort:\n");
    for(i=0;i<8;i++)
    {
        printf("%d\t",data[i]);
    }
    QuickSort(data,8);
    printf("\nAfter Sort:\n");
    for(i=0;i<8;i++)
    {
        printf("%d\t",data[i]);
    }
    return 0;
}

void Swap(int *a,int *b)
{
    int tmp;
    tmp=*a;
    *a=*b;
    *b=tmp;
}

int Median3(int *data,int left,int right)
{
    int center=(left+right)/2;
    //确保data[left]<=data[center]<=data[right]
    if(data[left]>data[right])
        Swap(&data[left],&data[right]);
    if(data[left]>data[center])
        Swap(&data[left],&data[center]);
    if(data[center]>data[right])
        Swap(&data[center],&data[right]);

    Swap(&data[center],&data[right-1]);
    return data[right-1];
}

void QuickSort(int *data,int n)
{
    Qsort(data,0,n-1);
}

void Qsort(int *data,int left,int right)
{
    int i,j;
    int pivot;

    if(left+3<=right)//保证至少有4个数
    {
        pivot=Median3(data,left,right);
        i=left;
        j=right-1;
        for(;;)
        {
            while(data[++i]<pivot);
            while(data[--j]>pivot);

            if(i<j)
                Swap(&data[i],&data[j]);
            else
                break;
        }

        Swap(&data[i],&data[right-1]);
        Qsort(data,left,i-1);
        Qsort(data,i+1,right);
    }
    else
        InsertSort(data+left,right-left+1);//调用插入排序
}

void InsertSort(int *data,int N)
{
    int i=0,j=0;
    int tmp=0;

    for(i=1;i<N;i++)
    {
        tmp=data[i];//待插入的值
        for(j=i;j>0 && data[j-1]>tmp;j--)//在已排序数组中从后往前遍历,直到找到插入的位置j
            data[j]=data[j-1];
        data[j]=tmp;
    }
}





郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。