不正確的合併排序輸出

-4

我想在C++中使用模板函數編寫合併排序算法。輸出接近但不正確。我特別相信問題出在合併函數而不是合併排序函數。任何幫助將非常感激。這裏是我的代碼：不正確的合併排序輸出

template <class T1> 
void mergeSort(T1 array[], int lower, int upper) 
{ 
    if (lower < upper) 
    { 
     int middle = (lower + upper)/2; 

     mergeSort(array, lower, middle); 
     mergeSort(array, middle + 1, upper); 
     merge(array, lower, middle, upper); 
    } 
} 

template <class T1> 
void merge(T1 array1[], int lower, int middle, int upper) 
{ 
    int i = 0, 
     j = 0, 
     k = 0; 
    int size1 = middle - lower + 1; 
    int size2 = upper - middle; 
    T1* temp1 = new T1[size1]; 
    T1* temp2 = new T1[size2]; 

    for (int i = 0; i < size1; i++) 
    { 
     temp1[i] = array1[lower + i]; 
    } 
    for (int j = 0; j < size2; j++) 
    { 
     temp2[j] = array1[middle + 1 + j]; 
    } 

    while (i < size1 && j < size2) 
    { 
     if (temp1[i] < temp2[j]) 
     { 
      array1[k] = temp1[i]; 
      i++; 
     } 
     else 
     { 
      array1[k] = temp2[j]; 
      j++; 
     } 
     k++; 
    } 

    if (i == size1) 
    { 
     while (j < size2) 
     { 
      array1[k] = temp2[j]; 
      k++; 
      j++; 
     } 
    } 
    else 
    { 
     while (i < size1) 
     { 
      array1[k] = temp1[i]; 
      k++; 
      i++; 
     } 
    } 
} 

int main(){ 
    int a[] = { 7, 6, 4, 8, 1, 2, 3 }; 
    mergeSort(a, 0, 6); 
}

輸出：

1 1 2 2 3 3 8

來源

2016-09-19 SPFort

解決此類問題的正確工具是您的調試器。在*堆棧溢出問題之前，您應該逐行執行您的代碼。如需更多幫助，請閱讀[如何調試小程序（由Eric Lippert撰寫）]（https://ericlippert.com/2014/03/05/how-to-debug-small-programs/）。至少，您應該\編輯您的問題，以包含一個[最小，完整和可驗證]（http://stackoverflow.com/help/mcve）示例，該示例再現了您的問題，以及您在調試器。 –

你的輸出如何不正確？它給你一個沒有排序的結果嗎？它給了你一個排序結果，但沒有正確執行合併排序？在您的問題中發佈輸出示例會很有幫助。 – PrestonM

你似乎缺少'delete [] temp1;''delete [] temp2;'，是嗎？不是它會影響結果，但不要忘記釋放你分配的內容。 –

在你merge功能你不應該初始化k爲0，因爲它會寫合併的結果在錯誤的地方。相反，您應該初始化k至lower。因爲那是你實際排序的部分的開始索引。

來源

2016-09-19 20:45:55 Tempux

非常感謝，現在看來很明顯！ – SPFort

不正確的合併排序輸出

回答

相關問題