0

我正在尝试使用以下合并排序函数对数组进行排序。但是它没有给我预期的输出。它不会打印出正确/预期的输出，即

输入：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];
    }
}
4

3 回答 3

3

我认为这是造成问题的原因——

    //  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循环也需要用<=更新

于 2013-10-18T05:16:38.300 回答
1

您在处理索引限制时有些困惑。

表示范围的两种非常常见的方法是：

  1. 范围限制指向元素之间
  2. 范围限制指向元素

范围坐标系

在图片中，上面的编号是使用“元素之间的指向”方法，灰色的范围是(2, 5).

下面的编号是使用“指向元素”的方法，相同的范围是(2, 4).

作为个人喜好，我更喜欢“元素之间”的方法：例如，范围的大小是high-low，您可以轻松地表示空范围甚至倒置范围。然而，重要的是，在编写管理范围的代码时，如果您使用第一种或第二种方法，请始终保持头脑清醒。

在您的代码中存在这种混乱；例如，mergesort您正在检查是否

low + 1 < high

这意味着您正在使用“元素之间”方法，因为 whenhigh - low = 1意味着只有一个元素并且不需要排序。您还递归传递(low, mid)and (mid, high)：使用“元素之间”方法的另一个明显迹象，因为您肯定不想移动array[mid]两次。

但是，在相同的代码中，您正在传递函数0，并且array_size-1在主程序中，这清楚地表明在这种情况下您正在使用“指向元素”方法。

只需仔细检查您的所有索引和范围使用是否一致，代码就可以了。

于 2013-10-18T06:21:25.357 回答
0

根据您的示例代码，只应打印 5 个数字作为结果（因为const int SIZE=5）。

除此之外，请注意您将列表中最后一个元素的位置提供为“高”参数。

但是，在您的合并函数中，您的while(j < high)条件确保列表中的最后一个元素不会被排序，因为排序在到达它之前停止。

更新：合并函数末尾的 for 循环需要调整为也将最后一个（“高”）元素复制回数组a。

于 2013-10-18T05:14:45.390 回答