问题描述

大神们帮我看看这个归并排序代码，谢了。

#include
using namespace std;
void fenkai(int a[], int l, int r);
void guibing(int a[], int start, int mid, int end);
int main(){
int a[20];
for (int i = 0; i < 20; i++){
a[i] = rand() % 100;
cout << a[i] << " ";
}
cout << endl;
fenkai(a, 0,19);
for (int i = 0; i < 20; i++)
cout << a[i] << " ";
}
void guibing(int a[], int start, int mid, int end){
int i, j, k;
i = start, j = mid + 1, k = 0;
int *c=new int[end-start+1];
while (i <= mid&&j <= end){
if (a[i] < a[j])
c[k++] = a[i++];
else
c[k++] = a[j++];
}
while (i<=mid)
c[k++] = a[i++];
while (j<=end)
c[k++] = a[j++];
for (int i = start, k = 0; i<(end-start+1); i++, k++)
a[i] = c[k];
delete[] c;
}
void fenkai(int a[],int l,int r){
if (l < r){
int m = (l + r) / 2;
fenkai(a, l, m);
fenkai(a, m+1, r);
guibing(a, l, m, r);
}
}

解决方案

改了三处：
1.多传入了一个参数int c[]作为目标数组
2.guibing函数里k初始成start
3.guibing函数最后的for循环改成了for(i=start; i<=end; i++)a[i] = c[i];

 #include<iostream>
using namespace std;
void fenkai(int a[], int c[], int l, int r);
void guibing(int a[], int c[], int start, int mid, int end);
int main(){
    int a[20], c[20];
    for (int i = 0; i < 20; i++){
        a[i] = rand() % 100;
        cout << a[i] << " ";
    }
    cout << endl;
    fenkai(a, c, 0,19);
    for (int i = 0; i < 20; i++)
        cout << c[i] << " ";
}
void guibing(int a[], int c[], int start, int mid, int end){
    int i, j, k;
    i = start, j = mid + 1, k = start;
    //int *c=new int[end-start+1];
    while (i <= mid&&j <= end){
        if (a[i] < a[j])
            c[k++] = a[i++];
        else
            c[k++] = a[j++];
    }
    while (i<=mid)
            c[k++] = a[i++];
    while (j<=end)
            c[k++] = a[j++];
    //for (int i = start, k = 0; i<(end-start+1); i++, k++)
    for(i=start; i<=end; i++)
        a[i] = c[i];
    //delete[] c;
}
void fenkai(int a[],int c[], int l,int r){
    if (l < r){
        int m = (l + r) / 2;
        fenkai(a, c, l, m);
        fenkai(a, c, m+1, r);
        guibing(a, c, l, m, r);
    }
}