排序算法——快速排序

参考书籍：《数据结构与算法分析——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;
    }
}