devbox
Gausst松鼠会
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

排序方式（8种）详解5—归并排序

作者：Gausst松鼠会 | 2024-04-15 21:01:45

赞

踩

排序方式（8种）详解5—归并排序

目录

1、归并排序概述

速度仅次于快速排序，为稳定排序算法，

原理：

图示：

时间和空间复杂度：

2、归并排序分类 

归并排序(循环版)、归并排序(递归版)

3、代码实现及运行结果

main函数：

归并排序(循环版)

归并排序(递归版)

小 tip:

关于c[i++]的理解：

先c[i],后i++。

留言：为作者一人拙见，仅参考使用，如有帮助，不甚荣幸。

1、归并排序概述

归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

速度仅次于快速排序，为稳定排序算法，

原理：

归并操作，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。

如　设有数列{6，202，100，301，38，8，1}

初始状态：6,202,100,301,38,8,1

第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；

第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；

第三次归并后：{1,6,8,38,100,202,301},比较次数：4；

总的比较次数为：3+4+4=11；

逆序数为14；

图示：

时间和空间复杂度：

时间复杂度：O(nlogn)

空间复杂度：O(n)

2、归并排序分类 

归并排序(循环版)、归并排序(递归版)

3、代码实现及运行结果

main函数：

  1. public static void main(String[] args) {
  2.         long  starttime1=System.nanoTime();
  3.         System.out.println("归并排序(递归版)");
  4.         int[] nums1=new int[]{4,4,6,77,33,45,55,90,30,67,3,1,2,3,4,5,6,68,98,99,76,65,66,33,43,32,43};
  5.         sort(nums1);
  6.         long endtime1=System.nanoTime();//200ns
  7.         System.out.println("程序运行时间："+(endtime1-starttime1)+"ns");
  8.  
  9.         long  starttime2=System.nanoTime();
  10.         System.out.println("归并排序(循环版)");
  11.         int[] nums2=new int[]{4,4,6,77,33,45,55,90,30,67,3,1,2,3,4,5,6,68,98,99,76,65,66,33,43,32,43};
  12.         sort1(nums2);
  13.         long endtime2=System.nanoTime();//200ns
  14.         System.out.println("程序运行时间："+(endtime2-starttime2)+"ns");
  15.     }

归并排序(循环版)

代码：

  1. //将数组中任意连续段赋值给另一数组
  2.     public static void copy1(int[]arr,int[]arrtmp,int start,int end){
  3.         for (int i = start; i <end ; i++) {
  4.             arr[i]=arrtmp[i];
  5.         }
  6.     }
  7.     //循环函数
  8.     public static void mergesort1(int[] arr,int[] arrtmp){
  9.         for (int flag = 1; flag <arr.length ; flag=flag*2) {
  10.             for (int start= 0; start<arr.length; start+=flag*2) {
  11.                 int min,mid,max;
  12.                 min=start;
  13.                 mid=Math.min(start+flag,arr.length-1);
  14.                 max=Math.min(start+flag*2,arr.length);
  15.                 int i=min;
  16.                 int start1=min,end1=mid;
  17.                 int start2=mid,end2=max;
  18.                 //将两个有序数列中最小值放置新数列中
  19.                 while(start1<end1&&start2<end2)arrtmp[i++]=arr[start1]<arr[start2]?arr[start1++]:arr[start2++];
  20.                 //将有序数列中剩余元素直接放于新数列尾部
  21.                 while(start1<end1)arrtmp[i++]=arr[start1++];
  22.                 while(start2<end2)arrtmp[i++]=arr[start2++];
  23.             }
  24.             //将新数列中有序部分复制给待排序数列arr
  25.             copy1(arr,arrtmp,0,arr.length);
  26.             //循环打印查看
  27.             for (int m = 0; m < arr.length; m++) {
  28.                 System.out.print(arrtmp[m]+",");
  29.             }
  30.             System.out.println();
  31.         }
  32.     }
  33.     //主函数2
  34.     public static void sort1(int[] num){
  35.         if(num.length<2)return;//输入数组过短直接返回
  36.         int[] arrtmp=new int[num.length];//临时存储已排序部分
  37.         mergesort1(num,arrtmp);
  38.     }

运行结果：

  1. 归并排序(循环版)
  2. 4,4,6,77,33,45,55,90,30,67,1,3,2,3,4,5,6,68,98,99,65,76,33,66,32,43,43,
  3. 4,4,6,77,33,45,55,90,1,3,30,67,2,3,4,5,6,68,98,99,33,65,66,76,32,43,43,
  4. 4,4,6,33,45,55,77,90,1,2,3,3,4,5,30,67,6,33,65,66,68,76,98,99,32,43,43,
  5. 1,2,3,3,4,4,4,5,6,30,33,45,55,67,77,90,6,32,33,43,43,65,66,68,76,98,99,
  6. 1,2,3,3,4,4,4,5,6,6,30,32,33,33,43,43,45,55,65,66,67,68,76,77,90,98,99,
  7. 程序运行时间：603300ns

归并排序(递归版)

代码：

  1. //将数组中任意连续段赋值给另一数组
  2.     public static void copy(int[]arr,int[]arrtmp,int start,int end){
  3.         for (int i = start; i <end+1 ; i++) {
  4.             arr[i]=arrtmp[i];
  5.         }
  6.     }
  7.  
  8.     //递归函数
  9.     public static void mergesort(int[]arr,int[]arrtmp,int start,int end){
  10.         if(start>=end)return;//分割序列至单个元素成有序序列时停止分割
  11.         //给两个新序列添加开头和结尾指标
  12.         int mid=start+(end-start)/2;
  13.         int start1=start,end1=mid;
  14.         int start2=mid+1,end2=end;
  15.         //递归调用分割
  16.         mergesort(arr,arrtmp,start1,end1);
  17.         mergesort(arr,arrtmp,start2,end2);
  18.         //归并有序数列
  19.         int i=start;
  20.         //将两个有序数列中最小值放置新数列中
  21.         while(start1<=end1&&start2<=end2)arrtmp[i++]=arr[start1]<arr[start2]?arr[start1++]:arr[start2++];
  22.         //将有序数列中剩余元素直接放于新数列尾部
  23.         while(start1<=end1)arrtmp[i++]=arr[start1++];
  24.         while(start2<=end2)arrtmp[i++]=arr[start2++];
  25.         //将新数列中有序部分复制给待排序数列arr
  26.         copy(arr,arrtmp,start,end);
  27.         //循环打印查看
  28.         for (int m = 0; m < arr.length; m++) {
  29.             System.out.print(arr[m]+",");
  30.         }
  31.         System.out.println();
  32.     }
  33.     //主函数1
  34.     public static void sort(int[] num){
  35.         if(num.length<2)return;//输入数组过短直接返回
  36.         int[] arrtmp=new int[num.length];//临时存储已排序部分
  37.         mergesort(num,arrtmp,0,num.length-1);//调用递归函数排序
  38.     }

运行结果：

  1. 归并排序(递归版)
  2. 4,4,6,77,33,45,55,90,30,67,3,1,2,3,4,5,6,68,98,99,76,65,66,33,43,32,43,
  3. 4,4,6,77,33,45,55,90,30,67,3,1,2,3,4,5,6,68,98,99,76,65,66,33,43,32,43,
  4. 4,4,6,77,33,45,55,90,30,67,3,1,2,3,4,5,6,68,98,99,76,65,66,33,43,32,43,
  5. 4,4,6,77,33,45,55,90,30,67,3,1,2,3,4,5,6,68,98,99,76,65,66,33,43,32,43,
  6. 4,4,6,77,33,45,55,90,30,67,3,1,2,3,4,5,6,68,98,99,76,65,66,33,43,32,43,
  7. 4,4,6,33,45,55,77,90,30,67,3,1,2,3,4,5,6,68,98,99,76,65,66,33,43,32,43,
  8. 4,4,6,33,45,55,77,30,90,67,3,1,2,3,4,5,6,68,98,99,76,65,66,33,43,32,43,
  9. 4,4,6,33,45,55,77,30,90,3,67,1,2,3,4,5,6,68,98,99,76,65,66,33,43,32,43,
  10. 4,4,6,33,45,55,77,3,30,67,90,1,2,3,4,5,6,68,98,99,76,65,66,33,43,32,43,
  11. 4,4,6,33,45,55,77,3,30,67,90,1,2,3,4,5,6,68,98,99,76,65,66,33,43,32,43,
  12. 4,4,6,33,45,55,77,3,30,67,90,1,2,3,4,5,6,68,98,99,76,65,66,33,43,32,43,
  13. 4,4,6,33,45,55,77,1,2,3,3,30,67,90,4,5,6,68,98,99,76,65,66,33,43,32,43,
  14. 1,2,3,3,4,4,6,30,33,45,55,67,77,90,4,5,6,68,98,99,76,65,66,33,43,32,43,
  15. 1,2,3,3,4,4,6,30,33,45,55,67,77,90,4,5,6,68,98,99,76,65,66,33,43,32,43,
  16. 1,2,3,3,4,4,6,30,33,45,55,67,77,90,4,5,6,68,98,99,76,65,66,33,43,32,43,
  17. 1,2,3,3,4,4,6,30,33,45,55,67,77,90,4,5,6,68,98,99,76,65,66,33,43,32,43,
  18. 1,2,3,3,4,4,6,30,33,45,55,67,77,90,4,5,6,68,98,99,76,65,66,33,43,32,43,
  19. 1,2,3,3,4,4,6,30,33,45,55,67,77,90,4,5,6,68,76,98,99,65,66,33,43,32,43,
  20. 1,2,3,3,4,4,6,30,33,45,55,67,77,90,4,5,6,68,76,98,99,65,66,33,43,32,43,
  21. 1,2,3,3,4,4,6,30,33,45,55,67,77,90,4,5,6,68,76,98,99,65,66,33,43,32,43,
  22. 1,2,3,3,4,4,6,30,33,45,55,67,77,90,4,5,6,68,76,98,99,33,65,66,43,32,43,
  23. 1,2,3,3,4,4,6,30,33,45,55,67,77,90,4,5,6,68,76,98,99,33,65,66,32,43,43,
  24. 1,2,3,3,4,4,6,30,33,45,55,67,77,90,4,5,6,68,76,98,99,33,65,66,32,43,43,
  25. 1,2,3,3,4,4,6,30,33,45,55,67,77,90,4,5,6,68,76,98,99,32,33,43,43,65,66,
  26. 1,2,3,3,4,4,6,30,33,45,55,67,77,90,4,5,6,32,33,43,43,65,66,68,76,98,99,
  27. 1,2,3,3,4,4,4,5,6,6,30,32,33,33,43,43,45,55,65,66,67,68,76,77,90,98,99,
  28. 程序运行时间：6120500ns

小 tip:

关于c[i++]的理解：

代码：

  1.  public static void main(String[] args) {
  2.         int[] c=new int[]{0,0};
  3.         int i=0;
  4.         c[i++]=8;
  5.         System.out.println(c[0]+"  "+c[1]);
  6.     }

运行结果：

  1. 8  0
  2.  
  3. 进程已结束,退出代码0

先c[i],后i++。

留言：为作者一人拙见，仅参考使用，如有帮助，不甚荣幸。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/430060
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号