如题,求解答。~~~急急急~~~~~~小白折腾了好几天 |
|
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,我发现确实对三个数进行排序时出了问题 |