【快速排序】算法实现

时间：2011-04-27 来源：冬天的草

快速排序，是分治递归的应用。算法的时间复杂性为：O（nlogn）。算法的递归深度接近于logn。因此，所需要的工作单元为O（logn）。

//快速排序
#include<iostream.h>
int count=0;
void swap(int &a,int &b)
{
    int temp;
    temp=a;
    a=b;
    b=temp;
}
int split(int array[],int low,int high)
{
    int i=low;//保存枢点元素的位置,初始值为low
    int j;
    int x=array[low];

    for(j=low+1;j<=high;j++)
    {
        if(array[j]<=x)
        {
            i++;
            if(i!=j)
            {
                swap(array[i],array[j]);
            }
        }
    }
    swap(array[low],array[i]);
    return i;
}
void print(int array[],int n)
{
    for(int i=0;i<8;i++)
    {
        cout<<array[i]<<" ";
    }
    cout<<endl;
}
void quick_sort(int array[],int low,int high)
{
    int k;
    if(low<high)
    {
        k=split(array,low,high);
        quick_sort(array,low,k-1);
        quick_sort(array,k+1,high);
    }
}
void main()
{
    int array[]={5,8,4,9,3,6,7,2};
    quick_sort(array,0,7);
    print(array,7);
}