爲什麼我的合併排序不起作用？

Question

它編譯得很好，但是當它運行時，它會向列表中添加隨機數，以及現有數字的重複。我有幾個人來看這個，他們都不知道。

void mergeSort(int list[], int length) { 
    recMergeSort(list, 0, length - 1); 
} 

void recMergeSort(int list[], int first, int last) { 

    if (first < last) { 
     int mid = (first + last)/2; 
     recMergeSort(list, first, mid); 
     recMergeSort(list, mid + 1, last); 
     merge(list, first, last, mid); 
    } 
} 

void merge(int list[], int first, int last, int mid) { 

    int arraySize = last - first + 1; 
    int* tempList = new int[arraySize]; 
    int beginPart1 = first; 
    int endPart1 = mid; 
    int beginPart2 = mid + 1; 
    int endPart2 = last; 


    int index = beginPart1; 


    while (beginPart1 <= endPart1 && beginPart2 <= endPart2) { 
     if (list[beginPart1] < list[beginPart2]) { 
      tempList[index] = list[beginPart1]; 
      beginPart1++; 
     } 
     else { 
      tempList[index] = list[beginPart2]; 
      beginPart2++; 
     } 
     index++; 
    } 

    while (beginPart1 <= endPart1) { 
     tempList[index] = list[beginPart1]; 
     index++; 
     beginPart1++; 
    } 

    while (beginPart2 <= endPart2) { 
     tempList[index] = list[beginPart2]; 
     index++; 
     beginPart2++; 
    } 


    for (int i = first; i <= last; i++) { 
     list[i] = tempList[i - first]; 
    } 

    delete[] tempList; 
} 

Answer 1

在功能合併（），你錯誤地計算index變量：

假設開始= 10，中= 14，末端= 19（對於0總陣列尺寸.. 19，你的索引= 10，但tempList數組被索引爲0..9（因爲arraySize = last - first + 1 == 10）。

因此，你溢出tempList陣列，當你「合併」，你會得到數據損壞。

修正您的index變量爲基於0（而不是基於beginPart1）。

Answer 2

如果我在C＃中運行此我得到以下行的IndexOutOfRangeException：

    tempList[index] = list[beginPart1]; 

，如果你跟蹤它通過你可能流失一個緩衝區的末尾，因此某處的隨機數我看。

Answer 3

我覺得問題就在這裏：

int index = beginPart1; 

應該

int index = 0;