首页 / 算法 / 归并排序以及归并排序的优化
归并排序以及归并排序的优化
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了归并排序以及归并排序的优化,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1962字,纯文字阅读大概需要3分钟。
内容图文
1、归并排序的实现
归并排序也利用了分治法的思想,首先将序列分成左右两部分,将左右两部分分别排序,然后将有序的两个子序列进行合并(即merge操作),程序是递归进行的,主函数实现如下:
//归并排序主函数 void merge_sort(int* a,int first,int last){ int mid; if(first<last){ mid = (first+last)/2; merge_sort(a,first,mid); merge_sort(a,mid+1,last); //merge(a,first,mid,last); //merge操作方法1,普通的merge操作 improved_merge(a,first,mid,last); //meger操作方法2,优化的merge操作 } }待排序的子序列从first开始,以last结尾,递归调用merge_sort,当first==last的时候停止,然后将已经有序的子序列进行合并操作。
2、普通的merge操作
普通的merge操作在合并长度为k和m的子序列时,需要消耗k+m个空间来创建一个临时数组,空间复杂度为O(n),实现如下:
//将从first到mid的子串和从mid+1到last的子串合并 void merge(int* a,int first,int mid,int last){ int* c; int i = first,j = mid+1; int k = 0; //合并n个元素需要n个空间,空间复杂度为O(n) c = (int*)malloc(sizeof(int)*(last-first+1)); while(i<=mid && j<=last){ if(a[i]<=a[j]){ c[k++] = a[i++]; }else{ c[k++] = a[j++]; } } while(i<=mid){ c[k++] = a[i++]; } while(j<=last){ c[k++] = a[j++]; } for(i=first,k=0;i<=last;i++,k++){ a[i] = c[k]; } }3、优化的merge操作
在合并长度为k和m的子串时,只需要min{k,m}的额外空间即可,首先申请大小为min{k,m}的空间,然后从子序列a和b中选择最右边的元素(即从子序列最大元素开始选),选择两个子序列中的较大者放在额外空间的右边,从右向左填充,额外空间填满之后再填充长度为max{k,m}的子序列,从最后一个开始填充,这种方法省了至少一半的空间,虽然空间复杂度仍未O(n),实现如下:
//申请额外n/2个空间,如果两个子串大小不一样,则申请的空间 //大小只需要为小的那个。选取两个子串中的较大的从右往左排序。 //先填充额外空间c,再填充已有的空间。 void improved_merge(int* a,int first,int mid,int last){ int* c; int i,j,k; //合并n个元素需要需要n/2个空间,虽然空间复杂度仍为O(n) c = (int*)malloc(sizeof(int)*(last-mid)); i=mid,j=last; for(k=last-mid-1;k>=0;k--){ //从右往左填充c if(a[i]>=a[j]){ c[k] = a[i--]; }else{ c[k] = a[j--]; } } k = mid; while(i>=first&&j>=mid+1){ //填充a if(a[i]>=a[j]){ a[k--] = a[i--]; }else{ a[k--] = a[j--]; } } while(i>=first){ a[k--] = a[i--]; } while(j>=mid+1){ a[k--] = a[j--]; } for(i=mid+1,k=0;i<=last;i++,k++){ //将c复制到a中 a[i] = c[k]; } }4、归并排序的时间复杂度分析
进行一次merge操作,worst case需要进行k+m-1次比较,即若k+m=n,需要进行n-1次比较。
递归表达式可以近似表示为:
T(n)=T(n/2)+T(n/2)+Cn。
由master theorem可得为nlgn,空间复杂度由上面分析可得为O(n)。
原文:http://blog.csdn.net/x_i_y_u_e/article/details/44650047
内容总结
以上是互联网集市为您收集整理的归并排序以及归并排序的优化全部内容,希望文章能够帮你解决归并排序以及归并排序的优化所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。