注册 登录
编程论坛 C++教室

C++ 实现快速排序问题?

hcs_xiaohan 发布于 2016-12-06 21:56, 1255 次点击
程序目的如题,代码如下:
#include <iostream>
#include <cstdlib>
#include <algorithm>

using namespace std;

template <typename T>
void quicksort(T B[], int lo, int hi);
template <typename T>
int Partition(T B[], int lo, int hi);

int main() {

    int a[] = {6,5,0,1,34,9,4,4,4,2,-1};
    for(int i = 0; i < 11; i++)
        cout << a[i] << ",";
    cout << endl;

    quicksort(a, 0, 11);
   
    for(int i = 0; i < 11; i++)
        cout << a[i] << ",";
    cout << endl;

    return 0;
}

template <typename T>
void quicksort(T B[], int lo, int hi) {
    if(hi - lo < 2) return;
   
    int mi = Partition(B, lo, hi - 1);

    quicksort(B, lo, mi);
    quicksort(B, mi+1, hi);
}

template <typename T>
int Partition(T B[], int lo, int hi) {
    swap(B[lo], B[rand()%(hi - lo)]);
    T pivot = B[lo];

    while(lo < hi) {
        while(pivot <= B[hi])
            hi--;
        B[lo] = B[hi];

        while(B[lo] <= pivot)
            lo++;
        B[hi] = B[lo];
    }

    B[lo] = pivot;

    return lo;
}

运行结果如下:

6,5,0,1,34,9,4,4,4,2,-1,
1,0,2,4,-1,5,-309542368,20689408,9,34,-309542080,
*** stack smashing detected ***: ./test terminated
Aborted (core dumped)

请各位看看是哪儿错了?
1 回复
#2
rjsp2016-12-07 08:52
这种问题应该对照着正确的代码一行行的检查,别人没时间帮你做这些事

rand()%(hi - lo) 应该是 lo + rand()%(hi-lo)

while(pivot < B[hi])
    hi--;
hi 会越界,应该是 while( lo<hi && pivot < B[hi] )
下面那个while同样的道理

1