采用median3做快速排序,发现数组大小为偶数不能正确排序,而奇数时可以???

C语言 码拜 9年前 (2015-05-11) 1545次浏览 0个评论
 

如题,求解答。~~~急急急~~~~~~小白折腾了好几天

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);
    }
}

谢谢回复~~~,上面是我的代码,您帮我看看

引用 1 楼 zhangxiangDavaid 的回复:

这种轴值的选择只是一种策略,肯定可以排序,你的代码似乎有问题。

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];
}
引用 4 楼 zhangxiangDavaid 的回复:

对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做快速排序,发现数组大小为偶数不能正确排序,而奇数时可以???
喜欢 (0)
[1034331897@qq.com]
分享 (0)

文章评论已关闭!