一. 排序方法
- 归并排序(Merge Sort)是利用"归并"技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。
- 给定数组data[0...n],若data[0...m]和data[m+1...n]两个子数组均已经有序。
- 可以先将两个子数组合并到一个临时数组tmpAr[0...n]里面。
- 然后将tmpAr复制到原data数组里面。
- 合并过程
- 合并过程中,设置i,j和p三个指针,其初值分别指向这三个记录区(两个子数组和一个临时数组)的起始位置。
- 合并时依次比较data[i]和data[j]的关键字,取关键字较小的记录复制到tmpAr[p]中,然后将被复制记录的指针i或j加1,以及指向复制位置的指针p加1。
- 重复这一过程直至两个子数组有一个已全部复制完毕(不妨称其为空),此时将另一非空的数组中剩余记录依次复制到tmpAr中即可。
二.动画演示
http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/guibingpaixu.htm
三. Java代码
- /*将索引从left到right范围的数组元素进行归并排序
- * data 待排序数组
- * left 待排序数组的第一个元素索引
- * right 待排序数组的最后一个元素索引
- */
- public static void sort(int[] data, int left, int right) {
- // TODO Auto-generated method stub
- if(left<right){
- //找出中间索引
- int center=(left+right)/2;
- //对左边数组进行递归
- sort(data,left,center);
- //对右边数组进行递归
- sort(data,center+1,right);
- //合并
- merge(data,left,center,right);
- }
- }
- /*将两个数组进行归并,归并前两个数组已经有序,归并后依然有序
- * data 数组对象
- * left 左数组的第一个元素的索引
- * center 左数组的最后一个元素的索引,center+1是右数组第一个元素的索引
- * right 右数组的最后一个元素的索引
- */
- private static void merge(int[] data, int left, int center, int right) {
- // TODO Auto-generated method stub
- int [] tmpArr=new int[data.length];
- int mid=center+1;
- //third记录临时数组tmpArr的索引
- int third=left;
- int tmp=left;
- while(left<=center&&mid<=right){
- //从两个数组中取出最小的放入中间数组
- if(data[left] <= data[mid]){
- tmpArr[third++]=data[left++];
- }else{
- tmpArr[third++]=data[mid++];
- }
- }
- //剩余部分依次放入中间数组
- while(mid<=right){
- tmpArr[third++]=data[mid++];
- }
- while(left<=center){
- tmpArr[third++]=data[left++];
- }
- //将中间数组中的内容复制回原数组
- while(tmp<=right){
- data[tmp]=tmpArr[tmp++];
- }
- System.out.println(Arrays.toString(data));
- }
四. 时间复杂度和稳定性
- 时间复杂度
- 对长度为n的文件,需进行logn趟二路归并,每趟归并的时间为O(n),故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlogn)。
- 空间复杂度
- 归并排序需要一个辅助向量来暂存两有序子文件归并的结果,故其辅助空间复杂度为O(n),显然它不是就地排序。
- 归并排序是一种稳定的排序。
相关推荐
51单片机控制的循迹避障小车,支持红外遥控,可以实现前进后退左右和循迹切换
智能小车的相关功能例程,并且有程序的注释,
该套设备采用ZY6400-23.5/45型液压支架,最大采高达4.5 m。由于十二矿井下主要巷道断面较小,支架必须解体入井安装,回采结束后支架回撤又面临一个新课题。针对这个难题,十二矿改革回收工艺,采取相应的安全措施,顺利地...
ZY3-01星SC产品命名规范20160217.pdf
ZY-Player-Setup-2.6.4.exe
RF-SJ-ZY-04-F03 结构专业图纸审查标准及要点.zip
ZY-TP21便捷式打印机驱动是一款嵌入式微型打印机,这款打印机体积小,重量轻,噪音低,易集成,操作简单,可靠性强,这里介绍的正是针对这款打印机的驱动,ZY-TP21便捷式打印机驱动,有需要的朋友们快来下载吧。...
循迹小车的单片机程序。仅供参考大家互相学习,共同进步本次上传日志本次上传日志本次上传日志本次上传日志要求上传您自己觉得好的资料本次上传日志
不用换找资源,本身自带资源搜索的播放器
RF-SJ-ZY-04-F03 结构专业图纸审查标准及要点(1).zip
ZY-Player-Setup-2.6.1.exe
RF-GC-ZY-04-F03 管道打压验收标准.zip
zy-player PC端
RF-GC-ZY-04-F01 房屋验收记录单.zip
程序设计语言ZY1906-大作业.7z
ZY-Player清醒脱俗的一款播放器,无广告,速度快。
ZY5600-16-34型液压支架掩护梁有限元分析及其优化设计,蒲志新,邓全刚,以ZY5600-16-34型液压支架为研究对象,利用Pro/E软件对其液压支架进行三维建模,然后利用ANSYS软件对液压支架的强度进行有限元分析,并�
RF-SJ-ZY-04-F08 采暖通风设计图纸审查标准及要点(1).zip