学步园

快速排序，是分治递归的应用。算法的时间复杂性为：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);
}