快速排序算法不起作用

Question

我正在研究我正在研究的一个哈夫曼编码项目的快速排序算法（解释为什么所有的函数名称都以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); 
    }