数据结构之快排

推荐博客:http://developer.51cto.com/art/201403/430986.htm

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1000;
int a[maxn];
int mid;
int partsort(int *a,int low,int high)
{
    int gg=low;
    int flag=a[low];
    //printf("flag=%d\n",flag);
    while(low<high)
    {
        //printf("%d %d\n",a[low],a[high]);
        while(low<high&&a[high]>=flag) --high;
        while(low<high&&a[high]<=flag) ++low;
        //printf("%d %d\n",a[low],a[high]);
        swap(a[high],a[low]);
    }
    swap(a[gg],a[low]);
    //printf("low=%d %d\n",low,a[low]);
    return low;
}
void Qort(int *a,int low,int high)
{
    //printf("%d\n",low);
    if(low<high)
    {
        mid=partsort(a,low,high);
        //printf("    %d %d\n",low,mid-1);
        Qort(a,low,mid-1);
        Qort(a,mid+1,high);
    }

}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        memset(a,-1,sizeof(a));
        for(int i=1;i<=n;i++)
        {
            int w;
            scanf("%d",&a[i]);
        }
        Qort(a,1,n);
        for(int i=1;i<=n;i++)
        {
            printf("%d ",a[i]);
        }
    }
    return 0;
}
/*
3
3 2 1
*/

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注