快速排序算法不起作用

Question

我正在为我正在做的一个Huffman编码项目开发一个快速排序算法(这解释了为什么所有的函数名都以huff开头)。当使用调试器遍历它时，函数在找到最高项时似乎冻结了(当试图从向量的右侧找到“不应该”在那一侧的项时)。这段代码可能(可能还有)其他问题，但我现在将重点放在这个问题上。顺便说一句，大部分时间(所有时间)我调用cout是为了调试。

编辑:评论中对我的代码做了很多修改，但没有一个能解决我的问题。出于这个原因，我正在更新代码。

void huff_sort_partition(vector<Node*>* v, int b, int e){
    int tempt = b+((rand()%(e-b))+1);
    int p_idx = (*v)[tempt]->weight;
    cout << tempt << endl;
    int l = b+0;
    int r = e;
    cout << "P:" << p_idx << "  L-R:" << l << "-" << r << endl;
    while(l < r){
        while((*v)[l]->weight < p_idx){
            l++;
        }
        while((*v)[r]->weight > p_idx){
            r--;
        }
        Node* s = (*v)[b+l];
        (*v)[b+l] = (*v)[b+r];
        (*v)[b+r] = s;
    }

    huff_sort_partition(v, b, l-1);
    huff_sort_partition(v, l+1, e);
}
void Huff::huff_sort(vector<Node*>* v){
    srand ( time(NULL) );
    cout << "------sort------" << endl;
    huff_sort_partition(v, 0, v->size());
}

编辑:我想我应该加上这个，因为还没有人回答这个问题。如果代码“应该”工作，那么注释它(这样我就可以在代码之外寻找为什么它不能工作的原因)。

Answer 1

考虑当有几个节点具有轴权重时，代码中会发生什么-为简单起见，考虑权重[1, 9, 5, 2, 7, 5, 6, 8, 3, 7]，并可能轴心索引为5，因此

void huff_sort_partition(vector<Node*>* v, int b, int e){
    int p = (*v)[b+(rand() % (e - b + 1))]->weight;

我们有p = 5

    int l = 0;
    int r = e-b;

l = 0和r = 9

    cout << "P:" << p << "  L-R:" << l << "-" << r << endl;
    while(l < r){
        while((*v)[b+l]->weight < p){
            l++;
        }

1 < 5，然后递增l、l = 1、v[1] = 9 > 5。

        while((*v)[b+r]->weight > p){ // where it freezes up and wont move on
            r--;
        }

7 > 5，递减r，r = 8，v[8] = 3 < 5。交换v[1]和v[8]，给出[1, 3, 5, 2, 7, 5, 6, 8, 9, 7]。

下一轮，l = 1 < 8 = r。v[1] = 3 < 5，l变为2，v[2] = 5不小于5，循环结束。现在进入第二个内部循环，v[8] = 9 > 5，v[7] = 8 > 5，v[6] = 6 > 5；v[5] = 5不大于5，交换v[2]和v[5]，得到[1, 3, 5, 2, 7, 5, 6, 8, 9, 7]。

下一轮，l = 2 < 5 = r，v[2] = 5不小于5，v[5] = 5不大于5，交换v[2]和v[5]。哦，我们被卡住了。

防止这种情况的通常方法是交换枢轴，并使两个条件中的一个条件为弱不等式，还必须在内部循环中检查条件l < r，或者在所有条目相等的情况下，一个条目将在数组/向量的末尾运行。然后在分区之后，将轴心交换到正确的位置。

下面的代码使用标准方式(未经测试，可能会有输入错误)：

void huff_sort_partition(vector<Node*>* v, int b, int e){
    // Nothing to sort if there are fewer than two elements
    if (e <= b) return;
    int tempt = b+((rand()%(e-b))+1);
    int p_idx = (*v)[tempt]->weight;
    // swap pivot out of the way
    Node *tmp_Node = (*v)[tempt];
    (*v)[tempt] = (*v)[e];
    (*v)[e] = tmp_Node;
    cout << tempt << endl;
    int l = b;
    int r = e - 1;
    cout << "P:" << p_idx << "  L-R:" << l << "-" << r << endl;
    while(l < r){
        while((l < r) && (*v)[l]->weight < p_idx){
            l++;
        }
        while((l < r) && (*v)[r]->weight >= p_idx){
            r--;
        }
        if (l < r){
            Node* s = (*v)[l];
            (*v)[l] = (*v)[r];
            (*v)[r] = s;
            // stuff at l and r is okay now, we don't need to test again
            ++l;
            --r;
        }
    }
    // Now l is the first index with weight >= pivot weight,
    // swap pivot into place
    tmp_Node = (*v)[l];
    (*v)[l] = (*v)[e];
    (*v)[e] = tmp_Node;

    huff_sort_partition(v, b, l-1);
    huff_sort_partition(v, l+1, e);
}

Answer 2

您在b,l使用和停止条件方面有问题。b是从哪里开始的索引，e是从哪里停止的索引。因此，当您第一次为e调用函数时，您必须引用最后一个索引，而不是大小。此外，你在huff_sort_partition中缺少停止条件-为了不会永远运行，你应该检查b和e索引是否相对正常。

请尝试下面代码的修复版本

void huff_sort_partition(vector<Node*>* v, int b, int e){ 
        if (b >= e ) {
            return;
        }
        int p = (*v)[b+(rand() % (e - b + 1))]->weight; 
        int l = 0; 
        int r = e-b; 
        cout << "P:" << p << "  L-R:" << l << "-" << r << endl; 
        while(l < r){ 
            while((*v)[b+l]->weight < p){ 
                l++; 
            } 
            while((*v)[b+r]->weight > p){ 
                r--; 
            } 
            Node* s = (*v)[b+l]; 
            (*v)[b+l] = (*v)[b+r]; 
            (*v)[b+r] = s; 
        } 

        huff_sort_partition(v, b, b+l-1); 
        huff_sort_partition(v, b+r+1, e); 
        cout << "P:" << p << "  L-R:" << l << "-" << r << endl; 
        for_each(v->begin(), v->end(), show_freq); 
    } 
    void Huff::huff_sort(vector<Node*>* v){ 
        srand ( time(NULL) ); 
        cout << "------sort------" << endl; 
        huff_sort_partition(v, 0, v->size() - 1); 
    }