首页 > 代码库 > 算法之归并排序的递归与非递归的实现
算法之归并排序的递归与非递归的实现
一.什么是归并排序
归并排序就是将多个有序的数据段合成一个有序的数据段，如果参与合并的只有两个有序的数据段，则称为二路归并。与快速排序和堆排序相比，其最大的特点是一种稳定的算法，算法的平均时间复杂度O(nlog2n)。
二.归并排序的基本思路
(1).对于一个原始的待排序表，可以将R[1]到R[n]可以看做是n个长度为1的有序表，即分解。
(2).进行第一趟归并，即将上述的n个子序两两合并，得到 n/2向上取整 个有序表，若n为奇数，则归并到最后一个子序列长度为1，即合并。
(3).再将两个 n/2向上取整 个有序表两两合并，如此重复下去，直到得到一个长度为n的有序表，这种排序方法也叫2-路归并排序。
原理如下图
以[63，95，84，46，18，24，27，31，46]为例
三. 实现归并排序之前，需要调用"一次归并“和”一趟归并“，那什么是一次归并？什么是一趟归并呢？
（1）.一次归并：把首尾相接的两个有序表R[low...mid]、R[mid+1...high]归并成有序表R[low...high].
(2) .一趟归并：把一些相互连接的有序表依次两两归并成一些更大的有序表。
1.一次归并代码如下
//一次归并排序 void Merge(int low,int m,int high) { // 将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的子文件R[low..high] int i=low; int j=m+1; int p=0; //置初始值 int *R1; //R1是局部向量 R1=(int *)malloc((high-low+1)*sizeof(int)); if(!R1) //申请空间失败 { puts("空间申请失败"); return; } while(i<=m&&j<=high) // 两子文件非空时取其小者输出到R1[p]上 R1[p++]=(R[i]<=R[j])?R[i++]:R[j++]; while(i<=m) // 若第1个子文件非空，则复制剩余记录到R1中 R1[p++]=R[i++]; while(j<=high) // 若第2个子文件非空，则复制剩余记录到R1中 R1[p++]=R[j++]; for(p=0,i=low;i<=high;p++,i++) R[i]=R1[p]; // 归并完成后将结果复制回R[low..high] }
2.一趟归并排序代码如下
1 //一趟归并排序 2 void mergepass(int n,int len) 3 { 4 int i,t; 5 i=1; 6 while(i<=n-2*len+1) 7 { 8 Merge(i,i+len-1,i+2*len-1); 9 i=i+2*len;10 }11 if(i+len-1<n)12 Merge(i,i+len-1,n);13 }
写完”一次归并“和"一趟归并”后，接下来就是编写二路归并了，二路归并就是调用“一次归并”和“一趟归并”，最后组合成一个长度为n的有序表。
二路归并有递归的方法和非递归的方法（即迭代方法），下面就来看一下递归与非递归的实现
(1)非递归的方法
1 void mergesort(int n) //非递归的二路归并实现 2 { 3 int len; 4 int *R1; // R1是局部向量 5 len=1; 6 while(len<n) 7 { 8 mergepass(n,len); 9 len=2*len;10 }11 }
(2)递归方法实现
1 //递归的二路归并排序 2 void MergeSortDC(int low,int high) 3 { //用分治法对R[low..high]进行二路归并排序 4 int mid; 5 if(low<high) 6 { // 区间长度大于1 7 mid=(low+high)/2; //分解 */ 8 MergeSortDC(low,mid); // 递归地对R[low..mid]排序 9 MergeSortDC(mid+1,high); //递归地对R[mid+1..high]排序 10 Merge(low,mid,high); // 组合，将两个有序区归并为一个有序区 11 } 12 }
讲到这里，归并排序的思想方法就讲完了，然后就可以自己写main()函数了，然后调用上面的自定义函数就可以实现了
下面是完整的代码实现，仅供参考,如有问题，欢迎指教
1 #include <stdio.h> 2 #include<malloc.h> 3 #include<stdlib.h> 4 #define MAX 100 5 int R[MAX]; 6 //一次归并排序 7 void Merge(int low,int m,int high) 8 { // 将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的子文件R[low..high] 9 int i=low; 10 int j=m+1; 11 int p=0; //置初始值 12 int *R1; //R1是局部向量 13 R1=(int *)malloc((high-low+1)*sizeof(int)); 14 if(!R1) //申请空间失败 15 { 16 puts("空间申请失败"); 17 return; 18 } 19 while(i<=m&&j<=high) // 两子文件非空时取其小者输出到R1[p]上 20 R1[p++]=(R[i]<=R[j])?R[i++]:R[j++]; 21 while(i<=m) // 若第1个子文件非空，则复制剩余记录到R1中 22 R1[p++]=R[i++]; 23 while(j<=high) // 若第2个子文件非空，则复制剩余记录到R1中 24 R1[p++]=R[j++]; 25 for(p=0,i=low;i<=high;p++,i++) 26 R[i]=R1[p]; // 归并完成后将结果复制回R[low..high] 27 } 28 //递归的二路归并排序 29 void MergeSortDC(int low,int high) 30 { //用分治法对R[low..high]进行二路归并排序 31 int mid; 32 if(low<high) 33 { // 区间长度大于1 34 mid=(low+high)/2; //分解 */ 35 MergeSortDC(low,mid); // 递归地对R[low..mid]排序 36 MergeSortDC(mid+1,high); //递归地对R[mid+1..high]排序 37 Merge(low,mid,high); // 组合，将两个有序区归并为一个有序区 38 } 39 } 40 //一趟归并排序 41 void mergepass(int n,int len) 42 { 43 int i,t; 44 i=1; 45 while(i<=n-2*len+1) 46 { 47 Merge(i,i+len-1,i+2*len-1); 48 i=i+2*len; 49 } 50 if(i+len-1<n) 51 Merge(i,i+len-1,n); 52 } 53 void mergesort(int n) 54 { 55 int len; 56 int *R1; // R1是局部向量 57 len=1; 58 while(len<n) 59 { 60 mergepass(n,len); 61 len=2*len; 62 } 63 } 64 void main() 65 { 66 int i,n,d; 67 puts("请输入数组的长度:"); 68 scanf("%d",&n); 69 if(n<=0||n>MAX) 70 { 71 printf("n 必须大于 0 小于 %d.\n",MAX); 72 exit(0); 73 } 74 puts("请依次输入数组的数据:"); 75 for(i=1;i<=n;i++) 76 scanf("%d",&R[i]); 77 puts("排序前的数组数据为:"); 78 for(i=1;i<=n;i++) 79 printf("%4d",R[i]); 80 printf("\n\n 递归与非递归的合并排序 \n"); 81 printf("\n 1.递归合并排序 \n"); 82 printf("\n 2.非递归合并排序 \n"); 83 printf("\n请输入您的选择："); 84 scanf("%d",&d); 85 if(d==1) 86 { 87 MergeSortDC(1,n); 88 puts("\n递归归并排序后:"); 89 for(i=1;i<=n;i++) 90 printf("%4d",R[i]); 91 } 92 else if(d==2) 93 { 94 mergesort(n); 95 puts("\n非递归归并排序后:"); 96 for(i=1;i<=n;i++) 97 printf("%4d",R[i]); 98 } 99 else100 printf("您输入的菜单号有误！"); 101 }
算法之归并排序的递归与非递归的实现