使用向量合并排序（int）C ++

user5056973 发表于 Dev

用户5056973

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

标题：

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

}

非常感谢！

杀手

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

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