我要去哪裏錯功能邏輯

Question

我寫一個程序做的3.我的快速排序算法在這裏的中位數quicksorting：

void quickSort(vector<int> & a, int left, int right) { 
    if (left + 10 <= right) { 
     const int & pivot = median3(a, left, right); 

     int i = left, j = right -1; 
     for (; ;){ 
      while(a [++i] < pivot){} 
      while(pivot < a[--j]){} 
      if(i < j) 
       swap(a[i], a[j]); 
      else 
       break; 
     } 
     swap(a[i], a[right-1]); 

     quickSort(a,left,i-1); 
     quickSort(a,i+1,right); 
    } 
} 

我產生的向量進行排序（排序僅矢量[0]雖然）

vector<vector<int> > vectorList; 

for (unsigned int j = 0; j < 8; j++) { 
    vector<int> tmp(100*pow(2,j)); 

    for (unsigned int l = 0; l<tmp.size(); l++) 
     tmp[l] = (rand() % 20000); 

    vectorList.push_back(tmp); 

而且從主在這裏我要快速排序呼叫：

quickSort(vectorList[0], 0, vectorList[0].size()-1); 

我的計劃目前將打印取出隨機值，但實際上將值排序出來有困難。我認爲我有一切正確的算法明智，但顯然不是。我已經經歷過多次，並且無法弄清楚問題所在。是否有任何新的眼睛能夠發現問題並就如何糾正問題提供一些建議？非常感謝！

Answer 1

假設這是Hoare分區方案，並且median3可以處理長度爲1個以上的元素。來自原文的評論改變。被描述爲「與原始相同的邏輯」的評論只是表面上的改變，從上面的原始示例中，這些行的代碼的邏輯沒有改變。 if（left + 10 < = right）和j = right-1是唯一真實的錯誤，但這個例子遵循典型的Hoare分區方案風格。

快速排序的

的工作實施可能會非常棘手，因爲一個小錯誤可能僅會失敗可能永遠不會得到測試特定的模式。

void quickSort(vector<int> & a, int left, int right) { 
    if(left >= right)    // left < right (not left+10 <= right) 
     return;      // else nothing to do so return 
    int pivot = median3(a, left, right); 
    int i = left-1, j = right+1; // left-1 (not left), right+1 (not right-1) 
    while(1){      // same logic as original 
     while(a[++i] < pivot);  // same logic as original 
     while(a[--j] > pivot);  // same logic as original 
     if(i >= j)     // same logic as original 
      break;     // same logic as original 
     swap(a[i], a[j]);   // same logic as original 
    } 
    quickSort(a,left,j);   // use j (not i-1) 
    quickSort(a,j+1,right);   // use j+1 (not i+1) 
} 

例如median3

int median3(vector<int> & a, int left, int right) 
    int i = left, j = (left + right)/2, k = right; 
    if (a[k] < a[i]) 
     swap(a[k], a[i]); 
    if (a[j] < a[i]) 
     swap(a[j], a[i]); 
    if (a[k] < a[j]) 
     swap(a[k], a[j]); 
    return(a[j]); 
} 

最小改變原來的例子，典型的霍爾分區方案的風格。

void quickSort(vector<int> & a, int left, int right) { 
    if (left <= right) {       // not (left+10 <= right) 
     int pivot = median3(a, left, right); // const ... & ?? 
     int i = left-1, j = right +1;   // left-1, right+1 
     for (; ;){ 
      while(a [++i] < pivot){} 
      while(pivot < a[--j]){} 
      if(i < j) 
       swap(a[i], a[j]); 
      else 
       break; 
     } 
     // swap(a[i], a[right-1]);    // deleted this line 
     quickSort(a,left,j);      // j instead of i-1 
     quickSort(a,j+1,right);     // j+1 instead of i+1 
    } 
}