算法笔记之归并排序
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法笔记之归并排序,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2753字,纯文字阅读大概需要4分钟。
内容图文
4 、归并排序
4.1 算法思想——
将数组分为两半,对每部分递归地应用归并排序,直到最后的子数组只包含一个元素。在每部分都排好序后,对它们进行合并。
4.2 时间复杂度——
假如用 T ( n )表示使用归并排序对 n 个元素构成的数组进行排序而使用的时间,用 mergeTime 来表示将两个子分组合并起来而花费的时间。那么
T ( n ) = T(n/2)+T(n/2) + mergetime
而 mege Time 就是归并两个子数组所耗费的时间,以最大时间来算,最多需要 n-1 次来比较两个子数组的元素,然后 n 次移动到临时数组中。那么 mergetime 就是 2n -1 。
因此 T ( n ) = T(n/2)+ T(n/2) +2n -1 。
使用数学知识可以求解到 T(n)= O(nlogn) 。
明显,归并排序优异于前面的选择,插入和冒泡算法。
应该注意到一点,就是我们平常用的工具类 java .util.Array 中 sort 方法就是使用归并排序的。
4.3 实现程序——
package lin.algo; public class Main { public static void main(String[] args) { int[] list = {255555553,1,-12222222,34,0,-101777770,991221299,235645452,047777745,145555000,-235551234, 255555553,1,-12222222,34,0,-101777770,991221299,235645452,047777745,145555000,-235551234, 255555553,1,-12222222,34,0,-101777770,991221299,235645452,047777745,145555000,-235551234, 255555553,1,-12222222,34,0,-101777770,991221299,235645452,047777745,145555000,-235551234, 255555553,1,-12222222,34,0,-101777770,991221299,235645452,047777745,145555000,-235551234, 255555553,1,-12222222,34,0,-101777770,991221299,235645452,047777745,145555000,-235551234}; long time = System.currentTimeMillis(); mergeSort(list); for (int i : list) { System.out.print(i+" "); } System.out.println(); System.out.println("归并排序所用时间是:"+(System.currentTimeMillis() - time)); } /* * 归并排序,分两步,一是分组,二是合并 */ private static void mergeSort(int[] list){ if (list.length<=1) { return; }else { //第一组,先排序 int[] firstList = new int[list.length/2]; //把前面一半的数据复制过去 System.arraycopy(list, 0,firstList,0, firstList.length); //递归地分组然后排序 mergeSort(firstList); //第二组,另一半 int[] secondList = new int[list.length-firstList.length]; //把前面一半的数据复制过去 System.arraycopy(list, firstList.length,secondList,0, secondList.length); //递归地分组然后排序 mergeSort(secondList); //将排好序的两个小组合并成一个有序的大组 int[] result = merge(firstList, secondList); //将最后结果复制到list中 System.arraycopy(result, 0, list, 0, result.length); } } /* * 归并排序第二步,合并 */ private static int[] merge(int[] firstList,int[] secondList){ int[] resultList = new int[firstList.length+secondList.length]; //定义三个变量来作为索引变量 int firstIndex = 0; int secondIndex = 0; int resultIndex = 0; //如果两组长度不一,先把一组合并完。 while (firstIndex<firstList.length && secondIndex<secondList.length) { if (firstList[firstIndex]<secondList[secondIndex]) { resultList[resultIndex++] = firstList[firstIndex++]; //小的先入 }else { resultList[resultIndex++] = secondList[secondIndex++]; } } //有可能某一组比另外一组多,因此上述循环并没完全将元素添加到resultList中 while(firstIndex<firstList.length){ resultList[resultIndex++] = firstList[firstIndex++]; } while(secondIndex<secondList.length){ resultList[resultIndex++] = secondList[secondIndex++]; } return resultList; } }
原文:http://blog.csdn.net/linfeng24/article/details/38027911
内容总结
以上是互联网集市为您收集整理的算法笔记之归并排序全部内容,希望文章能够帮你解决算法笔记之归并排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。