问题描述

哪位大神知道我这个归并排序的代码究竟哪里出了问题？

代码如下：
找了好久，实在找不出哪里的问题：

 #include<stdio.h>
void merge(int s[],int a[],int start,int mid,int end)
{
    int i=start;
    int j=mid+1;
    int k=start;
    while(i<=mid && j<=end) {
        if(a[i]<a[j]) {
            s[k++]=a[i++];
        } else {
            s[k++]=a[j++];
        }
    }
    if(i<=mid) {
        s[k++]=a[i++];
    }
    if(j<=end) {
        s[k++]=a[j++];
    }
}

void merge_sort(int s[],int a[],int start,int end)
{
    int t[20];
    int mid;
    if(start==end) {
        s[start]=a[start];
    } else {
        mid=(start+end)/2;
        merge_sort(t,a,start,mid);
        merge_sort(t,a,mid+1,end);
        merge(s,t,start,mid,end);
    }
}

int main()
{
    int i;
    int n=5;
    int a[n],s[n];
    printf("Enter %d nimbers: n",n);
    for(i=0;i<n;i++) {
        scanf("%d",&a[i]);
    }
    printf("n");
    merge_sort(s,a,0,n-1);
    printf("The sorted order is: n");
    for(i=0;i<n;i++) {
        printf("%5d",s[i]);
    }
    printf("n");
    return 0;
}

解决方案

我看到你这个问题，刚开始还以为是二分法，摸了半天瞎。后来发现时归并排序，然后我发现我也不会，就调你的程序，查资料什么事归并排序。
然后发现其实问题很简单，
while(i<=mid) {
s[k++]=a[i++];
}
while(j<=end) {
s[k++]=a[j++];
}
这个地方粗一看觉得是对的，但是后来我细想，要是1个排序的数组：4 5 3。然后经过你的这段程序，
while(i<=mid && j<=end) {
if(a[i]<a[j]) {
s[k++]=a[i++];
} else {
s[k++]=a[j++];
}
}

Enter 5 nimbers:
5 4 3 2 1

0-4
0-2
0-1
0-0
1-1
0 0 1
4 5 0 0 0
2-2
0 1 2
3 4 0 0 0
3-4
3-3
4-4
3 3 4
3 4 0 1 2
0 2 4
1 2 3 0 0
The sorted order is:
1 2 3 0 0
第一次，把三排到最开始，i ++ 了，while就退出了，这是还有4 5没有合并，然后你下面的是if（），这就造成，最多只能加一个元素的情况，把5给
丢了。现在是3 4，然后合并了 1 2，成了 3 4 0 1 2，在排序的时候，把 1 2 先拍， 这时候while退出，然后 就合并了一个 3 ， 4 给丢了。换成 while
就行了。还有，定义数组要规范，然后还要初始化，这是规范化操作。我贴上了测试的数据。不知道你看不看得懂。

解决方案二：

 int main()
{
    int i;
    const int n=5;//修改
    int a[n],s[2*n];//修改

解决方案三：

你的程序的思路没啥问题，只是细节上。还有主函数中数组的定义也有问题，c/c++中不能像你那样的定义一个数组。如果你不知道要定义的数组多大，就
要动态的去建立数组，要么就一开始指定数组元素的个数。比如a【5】，不要像你程序那样子定义一个数组。
下面是一段自己写的归并排序的代码你参考下：
1 #include

2 #include
3 void merge(int A[],int begin,int mid,int end);//合并函数
4 void mergesort(int A[],int begin,int end);//归并排序函数
5 void PRINT(int A[],int n);//数组大于函数
6
7 int main()
8 {
9 int a[5] = {9,3,2,0,1};
10

11 PRINT(a,5);
12 mergesort(a,0,5);
13 PRINT(a,5);
14

15 return 0;
16 }
17
18 void PRINT(int A[],int n)//数组大于函数
19 {
20 int i;
21 for(i=0;i
22 {
23 printf("%d--",A[i]);
24
25 }
26
27 printf("n");
28 }
29
30 void merge(int A[],int begin,int mid,int end)//合并函数实现
31 {
32 int i = begin;//数组左端有序起始
33 int j= mid+1;//数组右端有序起始
34 int k = begin;//临时数组下标起始
35
36 int *T = (int *)malloc((end - begin+1)*sizeof(int)); //申请临时数组空间
37 while(i
38 {
39 if(A[i]40 T[k++] = A[i++];//把左端元素放入临时数组
41 if(A[i]>A[j])//如果左端元素大于右端元素
42 T[k++] = A[j++];//右端元素放入临时数组
43
44 }

51 for(i=begin,k=begin;k<end-begin+1;i++,k++)
52 {
53 A[i]=T[k];//把临时数组元素拷贝回原数组
54 }
55
56 free(T);//释放申请的临时空间
57 }
58
59
60 void mergesort(int A[],int begin,int end)
61 {
62
63 if(begin < end)//只要数组中元素超过一个
64 {
65 int mid = (begin+end)/2;//从中间开始划分
66 mergesort(A,begin,mid);//左端有序
67 mergesort(A,mid+1,end);//右端有序
68
69 merge(A,begin,mid,end);//归并
70 }
71 }

解决方案四：

void merge(int s[],int a[],int start,int mid,int end)
{
int i=start;
int j=mid+1;
int k=start;
while(i<=mid && j<=end) {
if(a[i]<a[j]) {
s[k++]=a[i++];
} else {
s[k++]=a[j++];
}
}
** while**(i<=mid) {
s[k++]=a[i++];
}
while(j<=end) {
s[k++]=a[j++];
}
}

这两个地方是while循环。