首页 > 代码库 > 算法（第四版）学习笔记（三）——归并排序
算法（第四版）学习笔记（三）——归并排序
归并排序 MERGE-SORT
时间复杂度：
空间复杂度：
一、原地归并排序
步骤：将两个已有序数组组合到一个数组中并排好序。
1 #include<stdio.h> 2 #include<malloc.h> 3 int *c; 4 void merge(int *a, int *b,int m,int n); 5 int main() 6 { 7 int n,m,sum,i; 8 scanf("%d",&n); 9 int *a=(int *)malloc(sizeof(int)*n); 10 int *b=(int *)malloc(sizeof(int)*m); 11 for(i=0;i<n;i++) 12 scanf("%d",&a[i]); 13 scanf("%d",&m); 14 for(i=0;i<m;i++) 15 scanf("%d",&b[i]); 16 sum=m+n; 17 18 c=(int *)malloc(sizeof(int)*sum); 19 merge(a,b,m,n); 20 21 for(i=0;i<sum;i++) 22 printf("%d ",c[i]); 23 return 0; 24 } 25 void merge(int *a, int *b,int m,int n) 26 { 27 int i,j,k,sum; 28 j=0; 29 k=0; 30 sum=m+n; 31 for(i=0;i<sum;i++) 32 { 33 if(j>=n) //数组a已全部归入数组c 34 c[i]=b[k++]; 35 else if(k>=m) //数组b已全部归入数组c 36 c[i]=a[j++]; 37 else if(a[j]<b[k]) //数组a当前元素比数组b小 ，数组a当前元素归入数组c 38 c[i]=a[j++]; 39 else //数组b当前元素比数组a小 ，数组b当前元素归入数组c 40 c[i]=b[k++]; 41 } 42 }
二、自顶向下归并排序
步骤：运用递归的方法，将数组平均分为两部分，进行排序，再将前部分再分为两部分，进行排序....直到数组被分为n组两个元素比较排序
1 #include<stdio.h> 2 #include<malloc.h> 3 int sort(int *a,int *b,int lo,int hi); 4 void merge(int *a,int *b ,int lo,int mid,int hi); 5 int main() 6 { 7 int n,i; 8 scanf("%d",&n); 9 int *a=(int *)malloc(sizeof(int )*n); 10 int *b=(int *)malloc(sizeof(int )*n); 11 for(i=0;i<n;i++) 12 scanf("%d",&a[i]); 13 sort(a,b,0,n-1); 14 for(i=0;i<n;i++) 15 printf("%d ",a[i]); 16 return 0; 17 } 18 int sort(int *a,int *b,int lo,int hi) 19 { 20 int mid=lo+(hi-lo)/2; 21 if(lo>=hi) return 0; 22 sort(a,b,lo,mid); 23 sort(a,b,mid+1,hi); 24 merge(a,b,lo,mid,hi); 25 } 26 void merge(int *a,int *b ,int lo,int mid,int hi) 27 { 28 int i,j,k; 29 k=mid+1; 30 j=lo; 31 for(i=lo;i<=hi;i++) 32 b[i]=a[i]; 33 for(i=lo;i<=hi;i++) 34 { 35 if(j>mid) //前半部全部归并 36 a[i]=b[k++]; 37 else if(k>hi) //后半部全部归并 38 a[i]=b[j++]; 39 else if(b[j]<b[k])//前半部当前元素并后半部元素小 40 a[i]=b[j++]; 41 else// 前半部当前元素并后半部元素大 42 a[i]=b[k++]; 43 } 44 }
改进后的自顶向上归并排序
1 #include<stdio.h> 2 #include<malloc.h> 3 int sort(int *a,int lo,int hi); 4 void merge(int *a,int lo,int mid,int hi); 5 int main() 6 { 7 int n,i; 8 scanf("%d",&n); 9 int *a=(int *)malloc(sizeof(int )*n); 10 for(i=0;i<n;i++) 11 scanf("%d",&a[i]); 12 sort(a,0,n-1); 13 for(i=0;i<n;i++) 14 printf("%d ",a[i]); 15 return 0; 16 } 17 int sort(int *a,int lo,int hi) 18 { 19 int mid=lo+(hi-lo)/2; 20 if(lo>=hi) return 0;//小数组只剩一个或零个元素 21 sort(a,lo,mid); 22 sort(a,mid+1,hi); 23 if(a[mid]>a[mid+1])//改进：当a[mid]<=a[mid+1]时前半部和后半部小数组直接组成有序大数组 24 merge(a,lo,mid,hi); 25 } 26 int less(int a,int b) 27 { 28 if(a<b) 29 return 1; 30 return 0; 31 } 32 void merge(int *a,int lo,int mid,int hi) 33 { 34 int i,j,temp; 35 //改进:插入排序处理小规模数组更快 36 for(i=0;i<=hi;i++) 37 { 38 temp=a[i]; 39 for(j=i-1;j>=0&&less(temp,a[j]);j--) 40 { 41 a[j+1]=a[j]; 42 } 43 a[j+1]=temp; 44 } 45 }
三、自底向上归并排序
步骤：将数组分为n个微型数组，每个微型数组中前半部和后半部均有 sz（sz初始值为1，最后一个微型数组不一定为2*sz长度）个元素进行排序，然后这个排好序的微型数组又做为一个半部与另一个微型数组进行归并排序（当前sz=2），依次进行。。。。
1 #include<stdio.h> 2 #include<malloc.h> 3 int *b; 4 void sort(int *a,int n); 5 void merge(int *a,int lo,int mid,int hi); 6 int main() 7 { 8 int n,i; 9 scanf("%d",&n); 10 int *a=(int *)malloc(sizeof(int )*n); 11 for(i=0;i<n;i++) 12 scanf("%d",&a[i]); 13 b=(int *)malloc(sizeof(int )*n); 14 sort(a,n); 15 for(i=0;i<n;i++) 16 printf("%d ", a[i]); 17 return 0; 18 } 19 void sort(int *a,int n) 20 { 21 int sz,lo,min; 22 for(sz=1;sz<n;sz+=sz) 23 { 24 for(lo=0;lo<n-sz;lo+=2*sz)//lo<n-sz保证每小组前半部和后半部都有元素 25 { 26 hi=lo+2*sz-1; 27 if(hi>n-1) 28 hi=n-1; 29 merge(a,lo,lo+sz-1,hi); 30 } 31 32 } 33 } 34 void merge(int *a,int lo,int mid,int hi) 35 { 36 int i,j,k; 37 k=mid+1; 38 j=lo; 39 for(i=lo;i<=hi;i++) 40 b[i]=a[i]; 41 for(i=lo;i<=hi;i++) 42 { 43 if(j>mid) //前半部全部归并 44 a[i]=b[k++]; 45 else if(k>hi) //后半部全部归并 46 a[i]=b[j++]; 47 else if(b[j]<b[k])//前半部当前元素并后半部元素小 48 a[i]=b[j++]; 49 else// 前半部当前元素并后半部元素大 50 a[i]=b[k++]; 51 } 52 }
优势：比较适合链表组织的数据
注：当数组长度为2的幂时，自顶向下和自底向上的归并排序所用的比较次数和数组访问次数正好相同，只是顺序不同。
参考资料：《算法第四版》
算法（第四版）学习笔记（三）——归并排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。