快速排序算法

feng1008wd 发布于 2013-10-29 17:33， 360 次点击

跟网上的其他版本几乎一模一样不知道怎么就是调试不出结果求大神们看看

程序代码：

#include<iostream>
using namespace std;

int Part(int* a,int low,int high){

    int temp=a[low];
    int j=high,i=low;
    while(low<high){
        while(a[high]>=temp&&high>low){
            high--;
        }
        a[low]=a[high];
        while(a[low]<=temp&&high>low){
            low++;
        }
        a[high]=a[low];
    }
    a[low]=temp;
    return low;

}

void qsort(int* a,int low,int high){
    int pivotpos;
    while(low<=high){
        pivotpos=Part(a,low,high);
        qsort(a,low,pivotpos-1);
        qsort(a,pivotpos,high);
    }
}
int main(){
    int sort[10]={23,29,18,89,5,0,35,23,67,78};
    qsort(sort,0,9);
    for(int i=0;i<10;i++){
        cout<<sort[i];
    }
    system("pause");
    return 0;
}

7 回复

feng1008wd2013-10-29 17:53

回复楼主 feng1008wd

更正一下Qiuck_sort(a,pivotpos,high);调整为Qiuck_sort(a,pivotpos+1,high);还是同样结果

期待追忆2013-10-30 13:34

楼主你厉害，还是递归写的。这好像要麻烦很多吧

yuccn2013-10-30 13:54

void qsort(int* a,int low,int high){
    int pivotpos;
    while(low<=high){
        pivotpos=Part(a,low,high);
        qsort(a,low,pivotpos-1);
        qsort(a,pivotpos,high);
    }
}
算法是否正确先不说
这个不是死循环来的吗？
没有看到 low 和high 有变化

你这个while 什么时候结束？

期待追忆2013-10-30 13:56

楼主我仔细想过了，你这个程序错在递归那，void qsort(int* a,int low,int high)就是这个函数错了。
我用笔按照你的程序试了下了，当执行完pivotpos=Part(a,low,high);这句的时候low=2，high=1.如果继续执行qsort(a,low,pivotpos-1);这句的话就错了
快速排序法你可以试试不用递归算算看，然后再考虑递归。

feng1008wd2013-10-31 18:57

回复 4楼 yuccn

后面的两次递归调用qsort(a,low,pivotpos-1); qsort(a,pivotpos,high);不是会把high和low的值传递过去吗不过好像确实是这里陷入死循环了大神还是好好帮我看看程序吧我看到网上一些版本也是这样写的这段就没改过

feng1008wd2013-10-31 19:25

回复 5楼期待追忆

是那句错了，不过好像不是你说的那样是陷入死循环了

feng1008wd2013-10-31 19:54

问题解决了把while(low<=high)改成if(low<=high) 我怎么这么混蛋把while看成跟if一样。。。。