0

我写了一个小项目来实现归并排序。这是我的代码：

template <typename T>
void merge(T arr[], int begin, int mid, int end)
{
    int len = end - begin + 1;
    T *temp = new T[len];
    int i = begin;
    int j = mid + 1;
    int k = 0;
    while (i <= mid && j <= end)
    {
        if(arr[i] <= arr[j])
            temp[k++] = arr[i++];
        else
            temp[k++] = arr[j++];
    }
    while (i <= mid)
        temp[k++] = arr[i++];
    while(j <= end)
        temp[k++] = arr[j++];

    memcpy(arr + begin, temp, len*sizeof(T));
}


//merge sort
template <typename T>
void mergeSort(T arr[], int begin, int end)
{
    if (begin >= end)
        return;

    int mid = (end + begin) / 2;
    mergeSort(arr, begin, mid);
    mergeSort(arr, mid + 1, end);
    merge(arr, begin, mid, end);
}

int main()
{
    const int N = 10;
    int arr[N];
    for_each(arr, arr + N, [](int &val){ val = rand() % 100; });

    copy(arr, arr+N, ostream_iterator<int>(cout, " "));
    cout<<endl;

    mergeSort(arr, 0, N - 1);

    copy(arr, arr+N, ostream_iterator<int>(cout, " "));
    cout<<endl;
}

有时我得到了正确的答案，有时我得到了错误的答案。这个问题困扰了我很多时间，什么时候可以帮忙找到bug？

4

2 回答 2

0

您在代码中犯的错误是在计算要排序的数组的长度时。Indeedint len = end - begin;为您提供了 9 的长度，而您的数组包含 10 个元素。

向函数发送索引时应该小心。所有std::函数都使用迭代器，并且end迭代器总是指示最后一个元素的过去。

我建议您考虑到这一点来更改您的代码，尝试调用mergeSort(arr, 0, N);您的 main 函数，让其他函数正常运行。

于 2013-08-08T12:25:03.343 回答
0

是的，rand() 实现在两个平台上都不同，这是 stackoverflow 中的旧帖子，请参考此处的链接

于 2013-08-08T12:20:46.583 回答