|
如题，求解答。~~~急急急~~~~~~小白折腾了好几天 |
|
| 20分 |
这种轴值的选择只是一种策略，肯定可以排序，你的代码似乎有问题。
|
void swap1(int *a,int *b){
int *temp;
temp = *a;
*a=*b;
*b=temp;
}
int median3(int a[],int left,int right){
int center = (left+right)/2;
if(a[left]>a[center]){
swap1(&a[left],&a[center]);
}
if(a[right]<a[center]){
swap1(&a[right],&a[center]);
}
if(a[left]>a[right]){
swap1(&a[left],&a[right]);
}
swap1(&a[center],&a[right-1]);
return a[right-1];
}
void quick_sort(int a[],int left,int right){
int pivot = median3(a,left,right);
int i=left;
int j=right-1;
int f;
// for(f=0;f<10;f++){
// printf("%d",a[f]);
// }
if(left+3<=right){//很小的数组使用插入排序比较快
for(;;){
// printf("%d",a[++i]);
// printf("%d",a[--j]);
while(a[++i]<pivot){}
while(a[--j]>pivot){}
if(i<j){
swap1(&a[i],&a[j]);
}
else{
break;
}
}
swap1(&a[i],&a[right-1]);
if(left<i-1){ quick_sort(a,left,i-1);}//必须加判断否则出错！
if(i+1<right){ quick_sort(a,i+1,right);}
}
else{
InsertionSort(a,right-left+1);
}
}
谢谢回复~~~，上面是我的代码，您帮我看看 |
|
void swap1(int *a,int *b){
int *temp;
temp = *a;
*a=*b;
*b=temp;
}
int median3(int a[],int left,int right){
int center = (left+right)/2;
if(a[left]>a[center]){
swap1(&a[left],&a[center]);
}
if(a[right]<a[center]){
swap1(&a[right],&a[center]);
}
if(a[left]>a[right]){
swap1(&a[left],&a[right]);
}
swap1(&a[center],&a[right-1]);
return a[right-1];
}
void quick_sort(int a[],int left,int right){
int pivot = median3(a,left,right);
int i=left;
int j=right-1;
int f;
// for(f=0;f<10;f++){
// printf("%d",a[f]);
// }
if(left+3<=right){//很小的数组使用插入排序比较快
for(;;){
// printf("%d",a[++i]);
// printf("%d",a[--j]);
while(a[++i]<pivot){}
while(a[--j]>pivot){}
if(i<j){
swap1(&a[i],&a[j]);
}
else{
break;
}
}
swap1(&a[i],&a[right-1]);
if(left<i-1){ quick_sort(a,left,i-1);}//必须加判断否则出错！
if(i+1<right){ quick_sort(a,i+1,right);}
}
else{
InsertionSort(a,right-left+1);
}
}
|
|
|
对median3作如下修改：
/*
[left, right]
返回a[left]、a[center]、a[right]的中间值
*/
int median3(int a[], int left, int right) {
int center = (left + right) / 2;
if (a[left] > a[center]) {
swap1(&a[left], &a[center]);
}
if (a[right] < a[center]) {
swap1(&a[right], &a[center]);
}
//if (a[left] > a[right]) {
// swap1(&a[left], &a[right]);
//}
if (a[left] > a[center]){
swap1(&a[left], &a[center]);
}
//swap1(&a[center], &a[right - 1]);
swap1(&a[center], &a[right]);
return a[right];
}
|
|
|
3Q，我发现确实对三个数进行排序时出了问题 |
|
CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明采用median3做快速排序，发现数组大小为偶数不能正确排序，而奇数时可以？？？！