问题分析:基于分治算法思想,从待排序记录序列中选择一个记录(通常选取第一个记录)为枢纽,其关键字设为看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;
}
© 现实给了梦想多少时间 | Powered by LOFTER