快速排序算法不起作用

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