1

我正在为我正在处理的 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());
}

编辑：我想我会添加这个，因为还没有人回答这个问题。如果代码“应该”工作，然后评论它（这样我可以在这个代码之外寻找它为什么不能工作的原因）。

4

2 回答 2

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);
}
于 2012-07-20T20:34:57.453 回答
1

您的b,l使用和停止条件有问题。 b是从哪里开始 patitione的索引，是从哪里停止的索引。因此，当您第一次调用函数时，e您必须引用 last index 而不是 size 。此外，您还缺少停止条件huff_sort_partition- 为了不永远运行，您应该检查索引是否b相e对于每个 0ther 正常。

请尝试下面的代码的固定版本 

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); 
    }
于 2012-07-20T20:27:17.817 回答