合并排序不正确的输出

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时，会出现一个清晰的标志，在这种情况下，您正在使用“指向元素”方法。

只需仔细检查一下，您的所有索引和范围使用情况是否一致，代码是否正常。