c++ - 快速排序算法不起作用

我正在为我正在研究的Huffman编码项目开发一种快速排序算法(解释为什么所有函数名都以huff开头)。当使用调试器遍历它时，该函数似乎在找到最高项时冻结(当尝试从 vector 的右侧找到“不应”在该侧的项时)。这段代码可能(可能有)其他问题，但是我现在只关注这一点。顺便说一句，在大多数情况下(所有时间)，我都将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());
}

编辑:我想我要添加此，因为还没有人回答。如果代码“应该”可以工作，请对其进行注释(这样，我可以在代码之外寻找原因，以了解其为何无法工作)。

最佳答案

考虑一下具有多个枢轴权重的节点时代码中会发生什么-为简单起见，请考虑权重[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，或者在所有条目都相等的情况下运行在数组/ vector 的末尾。然后，在分区之后，将透 View 交换到正确的位置。

以下代码使用标准方式(可能会引起误解，输入错误):

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

关于c++ - 快速排序算法不起作用，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/11585365/