归并排序
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了归并排序,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1951字,纯文字阅读大概需要3分钟。
内容图文
-
归并排序
归并排序的原理:归并排序是将一个集合分成两部分:part1和part2,分别对part1和part2进行排序(使用递归法,直到子集合的大小为1,则停止将集合拆分,此时因为子集合中只有一个元素,所以,这个子集合也就相当于已经拍好了顺序),最后将这两部分排好顺序的集合合并为一。
在编写代码的时候有几个注意点:
-
如何将集合分成两部分,各大小都为多少?
集合的第一部分为list.length/2;集合的第二部分为list.length-list.length/2;
-
集合的递归调用什么时候停止?
当子集合的大小为1时,则停止对集合划分,故在方法的一开始应该加上一个判断
If(list.length > 1){
};
代码实现:
上段代码的merge方法的作用是将两个集合合并为一个并返回。
代码实现:
private static int[] merge(int[] list1, int[] list2){ int[] temp = new int[list1.length + list2.length]; int currentPosition1 = 0; //遍历list1时使用的下标变量 int currentPosition2 = 0; //遍历list2时使用的下标变量 int currentPositionTemp = 0; //合并两个list时使用的下标变量
//将两个集合中的元素copy到临时变量中 while(currentPosition1 < list1.length && currentPosition2 < list2.length){ if(list1[currentPosition1] < list2[currentPosition2]){ //将小的元素放到前面。 temp[currentPositionTemp++] = list1[currentPosition1++]; }else { temp[currentPositionTemp++] = list2[currentPosition2++]; } } //运行到此处时,list1和list2中的至少其中一个list已经全部复制到临时集合中,但有可能list1中元素的数量小于list2中元素 //的数量,因此,需要将list1或者list2中的剩余的数据复制到临时集合中。 while(currentPosition1 < list1.length){ temp[currentPositionTemp++] = list1[currentPosition1++]; } while(currentPosition2 < list2.length){ temp[currentPositionTemp++] = list2[currentPosition2++]; } return temp; } |
测试代码:
public static void main(String[] args) { // TODO Auto-generated method stub int[] list = {1,29,1,2,90,1,0}; mergeSort(list); for(int temp : list){ System.out.print(temp + " "); } System.out.println(); } |
运行结果:
原文:https://www.cnblogs.com/feng9exe/p/10001797.html
内容总结
以上是互联网集市为您收集整理的归并排序全部内容,希望文章能够帮你解决归并排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。