使用向量的合并排序 (int) C++

Question

我似乎无法弄清楚我的代码有什么问题。正如标题所说，我正在尝试使用整数向量实现合并排序。

HEADER:

using Val = int;
using Container = std::vector<Val>;
using Iter = long;
void mergeSort(Container& arr, Iter start, Iter end);

.CPP（我在文件中包含了合并的定义，只是没有在此处显示）

void mergeSort(Container& arr, Iter start, Iter end) {

if (start >= end) return;

int mid = (start + end) / 2;

mergeSort(arr, start, mid);
mergeSort(arr, mid + 1, end);
merge(arr, start, end, mid);


}

void merge(Container& arr, Iter start, Iter end, Iter mid)
{

int len = end - start + 1;
int x = 0;
Container temp;

temp.resize(arr.size());

int i, j, k;
i = start;
k = start;
j = mid + 1;

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++];

for (k = 0; k < len; k++) arr[k + start] = temp[k];

}

非常感谢！

Answer 1

只看你的代码，我认为一个问题是 merge 函数中 k 的初始值。

如果你把临时值放在Container temp从位置0开始，那么你应该初始化k到0

k = 0;

或者如果您想要从 start 开始的位置，那么您需要将最后一个 for 循环更改为

for (k = start; k <= end; k++) arr[k] = temp[k];

但是，请 post 有关您遇到的问题的更多信息。它是编译错误吗？还是运行时错误？或者结果不符合你的期望？另外，展示你做了什么来解决这个问题:)

Answer 2

我认为您的代码可能存在四个问题。

您假设序列 <start,mid> 和 <mid+1,end> 已排序。如果此条件不成立（例如 merge(v,0,3,2) on {6,5,7,4}），算法将给出不正确的结果。
您在使用函数时使用了不正确的 end 值（例如数组 {6,5,7,4} 上的 merge(v,0,4,2)。您总是必须遍历 <0,size-1>。
如前所述，k 应始终初始化为 0。您想将排序序列插入到排序数组的开头。
您假设参数 mid 是数组中元素的 index，而不是 position。例如 merge(v,0,3,2) 会在 {1,6,2,4} 上产生不正确的结果，因为在函数中您对从索引 mid+1=2+1=3 到 3 的序列进行排序，其中仅包含 {4}。因此，你的第一部分{1,6,2}没有排序，这是你的算法所要求的。

解决方法是：

将k初始化为0。
检查是否 mid<end.
使用另一种排序算法对 <0,mid> 和 <mid+1,end> 进行排序。

使用向量的合并排序 (int) C++

Merge Sort Using Vectors (int) C++

c++

vector

int

mergesort