注册 登录
编程论坛 C语言论坛

合并排序,我的思路很清晰

潺潺的小河 发布于 2019-03-18 19:25, 1716 次点击
程序代码:
#include"stdio.h"
#include"stdlib.h"
#define N 8
void Merge(int A[],int first,int mind,int end);
void Merge_sorted(int A[],int first,int end);

void main()
{
    int A[N]={5,2,4,7,1,3,2,6};
    int i;
    Merge_sorted(A,0,N-1);
    for(i=0;i<N;i++)
    {
       printf("\t%d",A[i]);
    }
}
void Merge_sorted(int A[],int first,int end)
{
    int mind;
    if(first<end)
    {
         mind=(end-first)/2;
         Merge_sorted(A,first,mind);
         Merge_sorted(A,mind+1,end);
         Merge(A,first,mind,end);
    }
}
void Merge(int A[],int first,int mind,int end)
{
     int i,k=0,n=0;
     int *L,*R;
     L=(int*)malloc(sizeof(int)*(mind-first+1));
     R=(int*)malloc(sizeof(int)*(end-mind+1));
     //数组中的元素转移;
     for(i=first;i<mind;i++,k++)
     {
         *(L+k)=A[i];
     }
     k=0;
     for(i=mind+1;i<end;i++,k++)
     {
         *(R+k)=A[i];
     }
     //合并两数组
     k=0;
     for(i=first;i<end;i++)
     {
         if(*(L+k)<=*(R+n))
         {
             A[i]=*(L+k);
             k++;
         }
         else
         {
             A[i]=*(L+n);
             n++;
         }
     }
     //释放空间
     free(L);free(R);
}


但问题不知道 :哪里出错了
4 回复
#2
word1232019-03-18 21:55
#include"stdio.h"
#include"stdlib.h"
#define N 8
void Merge(int A[],int first,int mind,int end);
void Merge_sorted(int A[],int first,int end);

//整个数组分为前后两部分
//递归对两个部分排序
//合并:将数组前后两部分分到临时数组L和R中
//      比较L和R中的数字,较小的放回原数组
//      若其中一个数组已遍历完,直接放另一个数组的数字
void main()
{
    int A[N]={5,2,4,7,1,3,2,6};
    int i;
    Merge_sorted(A,0,N-1);
    for(i=0;i<N;i++)
    {
       printf("\t%d",A[i]);
    }
}
void Merge_sorted(int A[],int first,int end)
{
    int mind;
    if(first<end)
    {
         mind=(end+first)/2;    //+
         Merge_sorted(A,first,mind);
         Merge_sorted(A,mind+1,end);
         Merge(A,first,mind,end);
    }
}
void Merge(int A[],int first,int mind,int end)
{
     int i,k=0,n=0;
     int *L,*R;
     L=(int*)malloc(sizeof(int)*(mind-first+1));
     R=(int*)malloc(sizeof(int)*(end-mind));   //
     //数组中的元素转移;
     for(i=first;i<=mind;i++,k++)
     {
         *(L+k)=A[i];
     }
     k=0;
     for(i=mind+1;i<=end;i++,k++)   //
     {
         *(R+k)=A[i];
     }
     //合并两数组
     k=0;
     for(i=first;i<=end;i++)   //
     {
         if(k>=(mind-first+1)){
                A[i]=*(R+n);
                n++;
         }else if(n>=(end-mind)){
                A[i]=*(L+k);
                k++;
         }else if(k<(mind-first+1) && n<(end-mind))
         {
            if(*(L+k)<=*(R+n))
             {
                 A[i]=*(L+k);
                 k++;
             }
             else
             {
                 A[i]=*(R+n);    //
                 n++;
             }
         }
     }
     //释放空间
     free(L);free(R);
}
#3
潺潺的小河2019-03-19 13:22
回复 2楼 word123
感谢提醒!
#4
潺潺的小河2019-03-19 13:55
回复 2楼 word123
     R=(int*)malloc(sizeof(int)*(end-mind));//更新部分end-mind+1

这一部分 我理解不到 为什么不(end-mind+1) 在N=2的情况下,我就觉感有问题。
#5
word1232019-03-20 16:01
L和R不是分别保存数组的左右两部分吗,左边大小mind-first+1   右边大小end-mind  加起来就是end-first+1,刚好是数组的大小


如果N=2 => first=0 mind=0 end=1
前面first到mind mind-first+1只有一个数
后面mind到end  end-mind也只有一个数
1