無法在C++中實現合併排序

Question

我是新來的算法，我一直在嘗試合併排序工作，但它不會給出正確的輸出。沒有編譯錯誤，但我想它只是在某處出現了缺陷，在輸出中顯示隨機值作爲排序數組。

void merge_sort(int[], int, int); 
void merge(int[], int, int, int); 
void printarray(int[], int); 

int main() { 
    int Arr[100], num_of_elements; 
    cout << "Enter the number of elements (max 100): "; 
    cin >> num_of_elements; 
    cout << "Enter array elements: \n"; 
    for (int i = 0;i < num_of_elements;++i) 
     cin >> Arr[i]; 
    merge_sort(Arr, 0, num_of_elements - 1); 
    cout << "\nAfter Sorting (by Merge Sort):\n"; 
    printarray(Arr, num_of_elements); 
    cout << endl; 
    return 0; 
} 

void merge_sort(int arr[], int left, int right) { 
    if (left < right) { 
     int mid = (left + right)/2; 
     merge_sort(arr, left, mid); 
     merge_sort(arr, mid + 1, right); 
     merge(arr, left, mid, right); 
    } 
} 

void merge(int arr[], int left, int mid, int right) { 
    int i, j, k; 

    /* Calculate the lengths of the subarrays and copy the elements into them */ 
    int lenght_left = mid - left + 1; 
    int length_right = right - mid; 
    int *leftarray = new int[lenght_left]; 
    int *rightarray = new int[length_right]; 
    for (i = 0;i < lenght_left;++i) 
     leftarray[i] = arr[left + i]; 
    for (j = 0;j < length_right;++j) 
     rightarray[j] = arr[mid + 1 + j]; 

    /* Reordering the elements in the original array */ 
    for (k = left, i = 0, j = 0;k <= right;++k) { 
     if (leftarray[i] <= rightarray[j]) 
      arr[k] = leftarray[i++]; 
     else 
      arr[k] = rightarray[j++]; 
    } 

    /* Copy remaining elements into the array */ 
    while (i < lenght_left) 
     arr[k] = leftarray[i++]; 
    while (j < length_right) 
     arr[k] = rightarray[j++]; 
    delete[](leftarray); 
    delete[](rightarray); 
} 

void printarray(int arr[], int num) { 
    cout << "Displaying Elements in array: \n"; 
    for (int i = 0;i < num;i++) 
     cout << arr[i] << " "; 
} 

Answer 1

在你merge功能：

/* Reordering the elements in the original array */ 
for (k = left, i = 0, j = 0; k <= right; ++k) { 
//       ^^^^^^^^^^^ 
// It should be i < lenght_left && j < length_right 
    if (leftarray[i] <= rightarray[j]) 
     arr[k] = leftarray[i++]; 
    else 
     arr[k] = rightarray[j++]; 
} 

你使用來控制循環的條件是不正確的，條件應該是相對於你的leftarray和rightarray，它應該是，那當兩個陣列中的任何一個到達最後時，請將您的條件更改爲i < lenght_left && j < length_right。

而且在同一個函數複製剩餘的元素時：

/* Copy remaining elements into the array */ 
while (i < lenght_left) 
    arr[k] = leftarray[i++]; 
//  ^^^ 
while (j < length_right) 
    arr[k] = rightarray[j++]; 
//  ^^^ 

在這裏，你忘了增加k，將其更改爲k++。

Answer 2

有您做夫婦的錯誤：

1. 你需要檢查你不要去了數組的長度，當你合併

   即代替：

   for (k = left, i = 0, j = 0;k <= right;++k) 
   

   你應該有：

   for (k = left, i = 0, j = 0;k <= right && i <lenght_left && j<length_right;++k) 
   

2. 添加剩餘元素時，您忘記增加數組計數器。 即：

   while (i < lenght_left) 
       arr[k] = leftarray[i++]; 
   while (j < length_right) 
       arr[k] = rightarray[j++]; 
   

   你應該有：

   while (i < lenght_left) 
       arr[k++] = leftarray[i++]; 
   while (j < length_right) 
       arr[k++] = rightarray[j++];