以下快速排序代码不起作用,我不明白是什么原因。
#include <iostream>
using namespace std;
void exch(int a[],int i,int j){
int s=a[i];
a[i]=a[j];
a[j]=s;
}
int partition(int a[],int l,int h);
void quick(int a[],int l,int h){
if (h<=l) return ;
int j=partition(a,l,h);
quick(a,l,j-1);
quick(a,j+1,h);
}
int partition(int a[],int l,int h){
int i=l-1;
int j=h;
int v=a[l];
while(true){
while( a[++i]<v);
while(a[--j]>v) if (j==i) break;
if (i>=j) break;
exch(a,i,j);
}
exch(a,i,h);
return i;
}
int main(){
int a[]={12,43,13,5,8,10,11,9,20,17};
int n=sizeof(a)/sizeof(int);
quick(a,0,n-1);
for (int i=0;i<n;i++){
cout<<a[i]<<" ";
}
return 0;
}
输出
5 8 9 11 10 17 12 20 13 43
最佳答案
在你的partition
方法中,应该是
int v = a[h];
并且不是
int v = a[l];
[更新:我刚刚测试了更改后的代码,它工作正常,输出:
5 8 9 10 11 12 13 17 20 43
关于c++ - 快速排序实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7624843/