不正确的合并排序输出

-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

不正确的合并排序输出

回答

相关问题