============================================================================
// Name : Merge.cpp
// Author :
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#include <iostream>
using namespace std;
void Merge(int array[], int p, int r);
int main() {
int merge[10]={5, 3, 8, 9, 0, 1, 2, 4, 7, 6};
Merge(merge, 0, 10);
return 0;
}
void Merge(int array[], int p, int r){
int q = (r+p)/2;
int n = q-p;
int m = r-q;
int left_array[n];
int right_array[m];
for(int i = 0; i < n; i++ ){
left_array[i]=array[p+i];
}
for(int j = 0; j < m; j++){
right_array[j] = array[q+j];
}
int i=0;
int j=0;
for(int k = 0; k < r; k++){
if(left_array[i] <= right_array[j]){
array[k] = left_array[i];
i = i + 1;
}
else{
array[k] = right_array[j];
j = j + 1;
}
}
for(int i = 0; i < r; i++){
cout << array[i] << " ";
}
//return 0;
}
有问题的地方是在merge函数里,修改过的代码如下,注释里已标出修改原因: void merge(int a[],int t[],int s,int m,int mid){ int mark,i,bak; //增加一个bak来备份mid的初始值 mark=s; bak=mid; //备份mid的初始值 while(s<=bak && (mid+1)<=m)//s<=mid被修正为s<=bak,因为mid在循环体里会自增,会导致有些元素进行了重复的比较和赋值 { if(a[s]<=a[mid+1]) { t[mark]=a[s]; printf("%d ",t[mark]); mark++; s++; } else { t[mark]=a[mid+1]; printf("%d ",t[mark]); mark++; mid++; } } if(s<=bak)//改用bak的值进行剩余元素的拷贝 { for(i=s;i<=bak;i++) //改用bak的值进行剩余元素的拷贝 { t[mark]=a[i]; printf("%d ",t[mark]); mark++; } } if((mid+1)<=m) { for(i=(mid+1);i<=m;i++) { t[mark]=a[i]; printf("%d ",t[mark]); mark++; } } }
答案来源于网络
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。