我的合并排序实现 C++ 中的问题
Problem in My Merge Sort Implementation C++
我一直在学习归并排序算法,但遇到了一些麻烦。在我的实现中,输出中的一些数字丢失了,而另一些则重复了。我正在使用向量并遵循 Cormen 等人在算法简介中描述的算法。阿尔。和 Geeksforgeeks.
代码如下:
#include <iostream>
#include <vector>
using namespace std;
void merge_sort(vector<int>&, int, int);
void merge(vector<int>&, int, int, int);
int main() {
vector<int> A = {5, 2, 4, 6, 1, 3};
int p = 0;
int r = A.size() - 1;
merge_sort(A, p, r);
for(int num : A)
cout << num << " ";
return 0;
}
void merge_sort(vector<int>&A, int p, int r){
if(p >= r)
return;
int mid = (p+r)/2;
merge_sort(A, p, mid);
merge_sort(A, mid+1, r);
merge(A, p, mid, r);
}
void merge(vector<int>&A, int p, int mid, int r){
int numLeft = mid - p + 1;
int numRight = r - mid;
//create two new vectors
vector<int> left;
vector<int> right;
//copy elements over
for(int i = 0; i < numLeft; i++)
left.push_back(A[i]);
for(int j = mid+1; j < (mid+1+numRight); j++)
right.push_back(A[j]);
//compare elements from the two arrays
int i = 0;
int j = 0;
int k = 0;
while(i < numLeft && j < numRight){
if(left[i] <= right[j]){
A[k] = left[i];
i++;
}
else{
A[k] = right[j];
j++;
}
k++;
}
//check if one half terminated before the other
while(i < numLeft){
A[k] = left[i];
k++; i++;
}
while(j < numRight){
A[k] = right[j];
k++; j++;
}
}
输出:1 2 3 6 1 3
您的 merge
函数假定您使用 p=0
进行排序。您应该从 p
复制,而不是从 0 复制。然后从 p
:
开始用 k
放回去
//copy elements over
for (int i = p; i < p + numLeft; i++)
left.push_back(A[i]);
for (int j = mid + 1; j < (mid + 1 + numRight); j++)
right.push_back(A[j]);
//compare elements from the two arrays
int i = 0;
int j = 0;
int k = p;
我一直在学习归并排序算法,但遇到了一些麻烦。在我的实现中,输出中的一些数字丢失了,而另一些则重复了。我正在使用向量并遵循 Cormen 等人在算法简介中描述的算法。阿尔。和 Geeksforgeeks.
代码如下:
#include <iostream>
#include <vector>
using namespace std;
void merge_sort(vector<int>&, int, int);
void merge(vector<int>&, int, int, int);
int main() {
vector<int> A = {5, 2, 4, 6, 1, 3};
int p = 0;
int r = A.size() - 1;
merge_sort(A, p, r);
for(int num : A)
cout << num << " ";
return 0;
}
void merge_sort(vector<int>&A, int p, int r){
if(p >= r)
return;
int mid = (p+r)/2;
merge_sort(A, p, mid);
merge_sort(A, mid+1, r);
merge(A, p, mid, r);
}
void merge(vector<int>&A, int p, int mid, int r){
int numLeft = mid - p + 1;
int numRight = r - mid;
//create two new vectors
vector<int> left;
vector<int> right;
//copy elements over
for(int i = 0; i < numLeft; i++)
left.push_back(A[i]);
for(int j = mid+1; j < (mid+1+numRight); j++)
right.push_back(A[j]);
//compare elements from the two arrays
int i = 0;
int j = 0;
int k = 0;
while(i < numLeft && j < numRight){
if(left[i] <= right[j]){
A[k] = left[i];
i++;
}
else{
A[k] = right[j];
j++;
}
k++;
}
//check if one half terminated before the other
while(i < numLeft){
A[k] = left[i];
k++; i++;
}
while(j < numRight){
A[k] = right[j];
k++; j++;
}
}
输出:1 2 3 6 1 3
您的 merge
函数假定您使用 p=0
进行排序。您应该从 p
复制,而不是从 0 复制。然后从 p
:
k
放回去
//copy elements over
for (int i = p; i < p + numLeft; i++)
left.push_back(A[i]);
for (int j = mid + 1; j < (mid + 1 + numRight); j++)
right.push_back(A[j]);
//compare elements from the two arrays
int i = 0;
int j = 0;
int k = p;