排序算法——归并排序

avatar 2017年10月11日12:56:27 7 3574 views
博主分享免费Java教学视频，B站账号：Java刘哥 ，长期提供技术问题解决、项目定制：本站商品点此
归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。


分而治之



可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为log2n。


合并相邻有序子序列


再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。






代码实现

  1. package algorithm;
  3. public class Sort_merge {
  4.     //打印数组
  5.     public static void printArr(int[] arr) {
  6.         for (int i:arr)
  7.             System.out.print(i+" ");
  8.         System.out.println();
  9.     }
  11.     private static void merge(int[] arr,int left,int mid,int right,int[] temp){
  12.         int i = left;//左序列指针
  13.         int j = mid+1;//右序列指针
  14.         int t = 0;//临时数组指针
  15.         while (i<=mid && j<=right){
  16.             if(arr[i]<=arr[j]){
  17.                 temp[t++] = arr[i++];
  18.             }else {
  19.                 temp[t++] = arr[j++];
  20.             }
  21.         }
  22.         while(i<=mid){//将左边剩余元素填充进temp中
  23.             temp[t++] = arr[i++];
  24.         }
  25.         while(j<=right){//将右序列剩余元素填充进temp中
  26.             temp[t++] = arr[j++];
  27.         }
  28.         t = 0;
  29.         //将temp中的元素全部拷贝到原数组中
  30.         while(left <= right){
  31.             arr[left++] = temp[t++];
  32.         }
  33.         //打印每一轮排序的结果
  34.         printArr(arr);
  35.     }
  37.     private static void mergeSort(int[] arr,int left,int right,int []temp){
  38.         if(left<right){
  39.             int mid = (left+right)/2;
  40.             mergeSort(arr,left,mid,temp);//左边归并排序，使得左子序列有序
  41.             mergeSort(arr,mid+1,right,temp);//右边归并排序，使得右子序列有序
  42.             merge(arr,left,mid,right,temp);//将两个有序子数组合并操作
  43.         }
  44.     }
  47.     public static void main(String args[]) {
  48.         int[] arr = {6,1,2,7,9,3,4,5,10,8};
  49.         int []temp = new int[arr.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
  50.         mergeSort(arr,0,arr.length-1,temp);
  51.     }
  52. }





原文地址：图解排序算法(四)之归并排序



历史上的今天
十月
11日
  • 微信
  • 交流学习，资料分享
  • weinxin
  • 个人淘宝
  • 店铺名：言曌博客咨询部

  • (部分商品未及时上架淘宝)
avatar

发表评论

avatar 登录者：匿名
匿名评论，评论回复后会有邮件通知

  

已通过评论：2   待审核评论数：0
  1. avatar 择方
    回复 2018年03月16日 16:09:24

    博主很强

  2. avatar 访客
    回复 2017年10月13日 11:48:27

    来看看学习一下