由网友(如果我愿意相信)分享简介:我知道有合并排序很多实现,但这是我曾经读过的书算法导论。下面code是排序合并的是无法正常工作的实现:I know that there are many implementations of merge sort but this is one which I have read in the book "Intr...
我知道有合并排序很多实现,但这是我曾经读过的书算法导论。下面code是排序合并的是无法正常工作的实现:
I know that there are many implementations of merge sort but this is one which I have read in the book "Introduction to algorithms". The following code is an implementation of merge sort which is not working correctly:
#include <iostream>
using namespace std;
void merge(int*a, int p, int q, int r) { //function to merge two arrays
int n1 = (q - p); // size of first sub array
int n2 = (r - q); // size of second subarray
int c[n1], d[n2];
for (int i = 0; i <= n1; i++) {
c[i] = a[p + i];
}
for (int j = 0; j <= n2; j++) {
d[j] = a[q + j];
}
int i = 0, j = 0;
for (int k = p; k < r; k++) { // merging two arrays in ascending order
if (c[i] <= d[j]) {
a[k++] = c[i++];
} else {
a[k++] = d[j++];
}
}
}
void merge_sort(int*a, int s, int e) {
if (s < e) {
int mid = (s + e) / 2;
merge_sort(a, s, mid);
merge_sort(a, mid + 1, e);
merge(a, s, mid, e);
}
}
int main() {
int a[7] { 10, 2, 6, 8, 9, 10, 15 };
merge_sort(a, 0, 6);
for (auto i : a)
cout << i << endl;
}
这code不能正常工作。什么是错在这code?怎样才可以解决吗?
This code is not working correctly. What's wrong in this code? How can it be fixed?
推荐答案
有几件事情在你的逻辑实现了偏差。我已经表明他们明确如下:
There are couple of things gone wrong in the implementation of your logic. I have indicated them clearly below:
void merge(int*a,int p,int q,int r){ //function to merge two arrays
int n1= (q-p); // size of first sub array
int n2= (r-q); // size of second subarray
int c[n1+1],d[n2]; //you need to add 1 otherwise you will lose out elements
for(int i=0;i<=n1;i++){
c[i]=a[p+i];
}
for(int j=0;j<n2;j++){
d[j]=a[q+j+1];//This is to ensure that the second array starts after the mid element
}
int i=0,j=0;
int k;
for( k=p;k<=r;k++){ // merging two arrays in ascending order
if( i<=n1 && j<n2 ){//you need to check the bounds else may get unexpected results
if( c[i] <= d[j] )
a[k] = c[i++];
else
a[k] = d[j++];
}else if( i<=n1 ){
a[k] = c[i++];
}else{
a[k] = d[j++];
}
}
}
相关推荐
最新文章