合併排序算法無法正常工作

Question

作爲家庭作業的一部分，我需要能夠使用結構作爲主要參數來實現合併排序。直到今天還沒有熟悉合併類，我試圖寫我自己的實現。出於某種原因，我無法讓它工作。

這裏是我的代碼：

#include<iostream> 
#include<stdlib.h> 

using namespace std; 

struct MergeArgument 
{ 
    int *numArray; 
    int *tempArray; 
    int lowIndex, highIndex; 
}; 

void merge(MergeArgument*); 
void merge_sort(MergeArgument*); 

int main(int argc, char** argv) 
{ int SIZE = 25; 
    MergeArgument arg; 
    int arr[SIZE]; 
    int temp[SIZE]; 

    for(int k = 0; k < SIZE; k++) 
    { 
     arr[k] = rand() % 100; 
     cout << arr[k] << " "; 
    } 

    arg.numArray = arr; 
    arg.tempArray = temp; 
    arg.lowIndex = 0; 
    arg.highIndex = SIZE - 1; 

    cout << endl; 

    merge_sort(&arg); 

    cout << "Sorted array: \n"; 

    for (int i = 0; i < SIZE; i++) 
     cout << arr[i] << " "; 
    cout << endl; 

    return 0; 
} 

void merge_sort(MergeArgument *arg) 
{ int tempHigh, tempLow; 
    if(arg->lowIndex < arg->highIndex) 
    { 
     tempHigh = arg->highIndex; 
     tempLow = arg->lowIndex; 
     arg->highIndex = (tempHigh + tempLow)/2; 
     merge_sort(arg); 
     arg->highIndex = tempHigh; 
     arg->lowIndex = ((tempHigh + tempLow)/2) + 1; 
     merge_sort(arg); 
     arg->lowIndex = tempLow; 
     merge(arg); 
    } 

} 

void merge(MergeArgument *arg) 
{ int low = arg->lowIndex, mid = ((arg->lowIndex + arg->highIndex)/2), high = arg->highIndex; 
    int i = low, lowCounter = low, highCounter = mid + 1; 

    while((lowCounter <= mid) && (highCounter <= high)) 
    { 
     if(arg->numArray[lowCounter] < arg->numArray[highCounter]) 
     { 
      arg->tempArray[i] = arg->numArray[lowCounter]; 
      lowCounter++; 
     } 
     else 
     { 
      arg->tempArray[i] = arg->numArray[highCounter]; 
      highCounter++; 
     } 
     i++; 
    } 

    if (lowCounter < mid) 
    { 
     for (int k = lowCounter; k < mid; k++) 
     { 
      arg->tempArray[i] = arg->numArray[k]; 
      i++; 
     } 
    } 
    else 
    { 
     for (int k = highCounter; k <= arg->highIndex; k++) 
     { 
      arg->tempArray[i] = arg->numArray[k]; 
      i++; 
     } 

    } 

    for(int k = arg->lowIndex; k <= arg->highIndex; k++) 
    { 
     arg->numArray[k] = arg->tempArray[k]; 
    } 
} 

這裏是輸出我得到：

83 86 77 15 93 35 86 92 49 21 62 27 90 59 63 26 40 26 72 36 11 68 67 29 82  
Sorted array: 
11 -1216235240 15 0 21 26 -1079135248 26 27 -1079135396 29 -1216770650 35 -1216235240 49 -1216492084 59 0 68 72 82 83 0 86 82 

任何人都可以指出正是我做錯了嗎？

Answer 1

儘管您可能想考慮一些人們在使C++更像C++時所做的評論，但這與工作非常接近。毫無疑問，這來自來之不易的經驗，沒有足夠的時間回去做你應該做的事情。

我看到的問題是在這裏，在merge：

if (lowCounter < mid) 
{ 
    for (int k = lowCounter; k < mid; k++) 
    { 
     arg->tempArray[i] = arg->numArray[k]; 
     i++; 
    } 
} 

你可能想比較和對比在這裏的界限初始循環。