gpt4 book ai didi

c++ - 使用 vector 的合并排序 (int) C++

转载 作者:搜寻专家 更新时间:2023-10-31 01:38:03 32 4
gpt4 key购买 nike

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

标题:

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

}

非常感谢!

最佳答案

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

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

解决方案是:

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

关于c++ - 使用 vector 的合并排序 (int) C++,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33406765/

32 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com