June 2——快速排序,

问题分析:基于分治算法思想,从待排序记录序列中选择一个记录(通常选取第一个记录)为枢纽,其关键字设为看k1然后将关键字小于k1的关键字移到k1前面,而将关键字大于k1的记录移到k1的后面,结果将待排序的序列分为两个子表,最后将关键字k1的记录插入到其分界线的位置处。将这一过程称为一趟快速排序。然后按照此方方法,对两部分数据分别进行快速排序。

 

#include<iostream>
using namespace std;
int partition(int *a,int p,int r)
{
    int x,i,j;
    i=p;j=r;
    x=a[p];
    while(i<j)
    {
        while(a[j]>=x&&i<j)
            j--;
        a[i]=a[j];
        while(a[i]<=x&&i<j)
            i++;
        a[j]=a[i];
    }
    a[i]=x;
    return i;
}
void quicksort(int *a,int p,int r)
{
    if(p<r)
    {
        int q=partition(a,p,r);
        quicksort(a,p,q-1);
        quicksort(a,q+1,r);
    }
}

void print(int *a,int n)
{
    for(int i=0;i<n;i++)
    {
        if(i==0)
            cout<<a[i]<<" ";
        else
            cout<<" "<<a[i];
    }
    cout<<endl;
}
int main()
{
    int n,a[20];
    while(cin>>n,n)
    {
        for(int i=0;i<n;i++)
            cin>>a[i];
        quicksort(a,0,n-1);
        print(a,n);
    }
    return 0;
}


评论
热度 ( 1 )

© 现实给了梦想多少时间 | Powered by LOFTER