归并排序

递归的函数

void sort(int l, int r)

{

if(l<r)

{int m=(l+r)/2;

sort(l,m);//左面

sort(m+1,r);//右边

merge(l,m,r);

 

}}

1、随机给数组一排数字 把它存进全局数组arr[]中。

2、里面有6个数，我们定义一个 int m作为中间数值为 m=(l+r)/2 ,也就是m=(0+6)/2  ，这个m是作为中间数，我们把左面的设一个变量 int l, 右面设的变量为 int r。

 

3、我们看函数一步一步走 if(l<r)成立 ，往下 m=(l+r)/2  l为0，r为6 m=3 ,进左递归 sort(l,m);//左面，参数l,m 0和3传进去 递归第二层中 l为0，r=3。

第二层中  if(i<r)依然成立，继续 m=(0+3)/2 这里我们把m 4舍5入 为2，接着进左递归 sort(l,m);//左面 l,m 0和2传进去  递归第三层中 l为0，r=2。

第三层中 if(i<r)还是成立，m=(0+2)/2  m这次为零了 ，继续进左递归 sort(l,m);//左面  l,m 0和0传进去 递归第四层 ，l为0，r也为0。if(i<r)不成立，包含的内容不执行，此时递归可算到头了。返回到递归的上一层，执行sort(l,m);//左面  下面的sort(m+1,r);//右边

此层m为2，r为3  m+1,r 作为参数传递给sort(m+1,r);//右边 接着判断然后接着................................................

这里一张流程图概括

 

4、如果递归明白了，就需要我们排序合并。

排序合并排序

void merge(int z,int m,int y)

{  int i=z, j=m+1,k=z;

    while(i<=m&&j<=y)

      if(arr[i]<arr[j])

        arr1[k++]=arr[i++];

    else

       arr1[k++]=arr[j++];

 while(i<=m)

    arr1[k++]=arr[i++];

while(j<=y)

    arr1[k++]=arr[j++];

for(i=z;i<y;i++)

{arr[i]=arr[i];

}}

    因为merge函数是在 sort(l,m)和sort(m+1,r)的下面，然后我们回头看递归中最后一层是哪一层？ 是第三层，第三层的 l为0，m为0，r为2带入merge函数中

这里用到了辅助 数组arr1[]来暂时存放通过比较后放入的数据。参数 int z是左 ，int m是中 ，int y是右。

定义变量进行参数的赋值  int i=z, j=m+1,k=z 。

while(i<=m&&j<=y) i从左开始到arr数组中间m , j从中间加一的位置开始到arr数组的右边。

 

if(arr[i]<arr[j]) 开始比较。

小的放前面 2和1 小的放到arr1中。

    arr1[k++]=arr[i++];

    else

    arr1[k++]=arr[j++];    

下面两个while循环是对左右作比后避免出现左右比较数有剩余的情况。

while(i<=m)   

    arr1[k++]=arr[i++];

while(j<=y)

    arr1[k++]=arr[j++];

然后下面的for循环是对arr1数组中暂存的数据再赋值给arr数组中。

for(i=z;i<y;i++)

{arr[i]=arr[i];

}}  

 

这一层的merge执行完成之后回到上一层执行sort(m+1,r)函数内部的内容，然后再次返回上一层。

 

排序归并过程总览图    

根据上图参照的来看，计算机的执行过程大体是这样。                                                                                                                                                        

 

程序代码

#include<iostream>

#include<stdio.h>

using namespace  std:

int arr[10]={2,3,4,1,2,3,1,2,1,5};

int arr1[10];

void merge(int z,int m,int y)

{  int i=z, j=m+1,k=z;

    while(i<=m&&j<=y)

      if(arr[i]<arr[j])

        arr1[k++]=arr[i++];

    else

       arr1[k++]=arr[j++];

 while(i<=m)

    arr1[k++]=arr[i++];

while(j<=y)

    arr1[k++]=arr[j++];

for(i=z;i<y;i++)

{arr[i]=arr[i];

}}

void sort(int l, int r)

{

if(l<r)

{int m=(l+r)/2;

sort(l,m);

sort(m+1,r);

merge(l,m,r);

 

}}

int main(){

sort(0,9);

for(int i=0;i<10;i++)

  printf("%d",arr[i]);

}