C++ 使用向量实现合并排序

Question

我正在使用C++使用向量而不是数组来实现合并排序算法。我从原始算法逐步工作，但是当我编译时，我没有收到任何输出或错误消息。我认为我的"合并"功能有问题，但我找不到它。我是排序算法的新手，所以如果我的代码中有任何基本的误解或错误，请向我解释。

#include <iostream>
#include <vector>
using namespace std;
void mergeSort(vector<int>& numvec, int left, int right){
if(left < right){
int middle = left + (right - left) / 2;
mergeSort(numvec, left, middle);
mergeSort(numvec, middle + 1, right);
merge(numvec, left, middle, right);
}
}
int merge(vector<int>& numvec , int left, int mid, int right){
int i, j, k, temp[right-left+1];
i = left;
j = right;
k = mid + 1;
while(i <= mid && j <= right){
if(numvec[i] < numvec[j])
{
temp[k] = numvec[i];
k++;
i++;
}
else
{
temp[k] = numvec[j];
k++;
j++;
}
while(i <= mid){
temp[k] = numvec[i];
k++;
i++;
}   
while( j <= right){
temp[k] = numvec[j];
}
for(i = left; i <= right; i++){
numvec[i] = temp[i - left];
}
}
}

Answer 1

第一个问题在下面的代码中：

int merge(vector<int>& numvec , int left, int mid, int right)

你说你会返回一个整数，但从来没有返回过任何东西。 同样对于 mergeSort，您应该声明两个临时数组，一个用于右侧，一个用于左侧，以便您可以合并它们，但您从未这样做过。最后，下面的代码根本没有意义：

for(i = left; i <= right; i++){
numvec[i] = temp[i - left];
}

它看起来像黑匣子，只是神奇地不知从何而来，与 mergeSort 没有任何关系，如果你想改进其他人的代码，请确保你首先了解算法。

Answer 2

到目前为止，我在代码中可以找到的错误如下：

1. int merge(vector<int>& numvec , int left, int mid, int right)

   当您合并左向量和右向量时，您必须返回合并的向量 矢量而不是整数。

2. k = mid + 1

   k将从l而不是mid + 1开始，因为在任何级别上，我们将从左向量的第一个索引开始填充元素，而不是从右向量的第一个元素填充mid + 1。

此外，您需要声明两个向量，以便在一个向量中从左到

3. 中存储元素，在另一个向量中从左到右存储元素。

现在，如果您必须严格使用向量实现合并排序，那么您可以看到我的代码。

vector<int> merge(vector<int> l,vector<int> r)
{
vector<int> res;

int i=0;
int j=0;
while(i!=l.size() && j!=r.size())
{
if(l[i]<=r[j])
{
re.push_back(l[i++]);
}
else
{
re.push_back(r[j++]);
}
}

while(i!=l.size())
re.push_back(l[i++]);

while(j!=r.size())
re.push_back(r[j++]);

return res;
}


vector<int> merge_d(vector<int>&A, int s,int e)
{
if(s-e==0)
{
vector<int> t;
t.push_back(A[s]);
return t;
}

int m=(s+e)/2;

vector<int> l;
vector<int> r;
l=merge_d(A,s,m);
r=merge_d(A,m+1,e);

return merge(l,r);
}