合併排序不正確的輸出

Question

我想使用下面的合併排序函數來排序數組。然而，它沒有給我預期的產出。 它不會打印出正確/預期的輸出即

輸入：5,4,3,2,1
輸出：1,2,3,4,5

相反，它提供了：2,3 ，4,5,1,9,8,7,8,4,1,8,8,2。

#include <iostream> 
#include <cmath> 
#include <ctime> 
#include <cstdlib> 

using namespace std; 

void mergeSort(int a[], int low , int high,int res[]); 
void merge(int a[], int low , int mid , int high,int res[]); 
void mergeSort(int numbers[], int temp[], int array_size); 

const int SIZE=5; 

int main() { 

    int sorted[SIZE]; 
    for (int i=0; i<SIZE; i++) { 
     cout << "input numbers" <<endl; 
     cin >>sorted[i]; 
    } 
    int merge[SIZE]; 

    mergeSort(sorted,merge,SIZE); 

    for (int i=0; i<SIZE; i++) { 
     cout << merge[i]; 
    } 

    return 0; 
} 

void mergeSort(int numbers[], int temp[], int array_size) 
{ 
    mergeSort(numbers, 0, array_size-1, temp); 
} 

void mergeSort(int a[], int low , int high,int res[]) 
{ 
    int mid = (low + high) /2; 
    if (low + 1 < high) 
    { 
     // Sort sub-parts 
     mergeSort(a,low,mid,res); 
     mergeSort(a,mid,high,res); 

     // Merge back to "res" 
     merge(a,low,mid,high,res); 
    }else{ 
     res[low] = a[low]; 
    } 
} 

void merge(int a[], int low , int mid , int high,int res[]) 
{ 
    int i = low; 
    int j = mid; 
    int k = low; // Use "low" instead of 0. 

    while (i < mid && j < high) 
     if(a[i] < a[j]) 
      res[k++] = a[i++]; 
     else 
      res[k++] = a[j++]; 

    while (i < mid) 
     res[k++] = a[i++]; 

    while (j < high) 
     res[k++] =a[j++]; 

    // Copy back to "a" 
    for (int c = low; c < high; c++){ 
     a[c] = res[c]; 
    } 
} 

Answer 1

根據示例代碼，只有5的數字應被打印爲結果（因爲const int的SIZE = 5）。

除此之外，請注意您提供列表中最後一個元素的位置爲「高」參數。

然而，在您的合併功能，您而（j <高）條件確保在榜單最後一個元素不會進行排序，因爲在到達之前分揀站。

更新：合併函數結尾處的for循環需要進行調整，以將最後（「高」）元素複製回數組a。

Answer 2

我認爲這是造成問題的原因 -

// Sort sub-parts 
    mergeSort(a,low,mid,res); 
    mergeSort(a,mid,high,res); 

應該

// Sort sub-parts 
    mergeSort(a,low,mid,res); 
    mergeSort(a,mid+1,high,res); 

而且if (low + 1 < high)應改爲if (low < high)

此外while (i < mid && j < high)應該while (i <= mid && j <= high)單while循環在它下面也需要更新< =

Answer 3

在處理索引限制時存在一些混淆。

兩個非常常見的方式來表示的範圍是：

1. 範圍限制元件之間的指向
2. 範圍限制都指向元件

在圖片中的編號上面是使用「指向元素」的方法，灰色範圍爲(2, 5)。

下面的編號是使用「指向元素」的方法，而相同的範圍是(2, 4)。

作爲個人喜好，我更喜歡「元素之間」方法：例如範圍的大小是high-low，您可以輕鬆地表示空白範圍或甚至反向範圍。然而，重要的是，如果您在編寫管理範圍的代碼時使用第一種或第二種方法，則始終清楚地記住它們。

在你的代碼中有這樣的混淆;例如在mergesort要檢查是否

low + 1 < high 

，這意味着您正在使用的「元素之間」的方法，因爲當high - low = 1意味着只有一個元素，並且不需要排序。你也遞歸(low, mid)和(mid, high)：另一個明顯的跡象表明，使用「元素之間」的方法，因爲你肯定不想兩次移動array[mid]。

但是，在相同的代碼中，您在主程序中傳遞函數0和array_size-1時，會出現一個清晰的標誌，在這種情況下，您正在使用「指向元素」方法。

只需仔細檢查一下，您的所有索引和範圍使用情況是否一致，代碼是否正常。