排序算法——归并排序

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

 

 

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

 

 

  • 微信
  • 赶快加我聊天吧
  • weinxin
  • 博客交流群
  • 海纳百川,大家来水
  • weinxin
言曌

发表评论

:?::razz::sad::evil::!::smile::oops::grin::eek::shock::???::cool::lol::mad::twisted::roll::wink::idea::arrow::neutral::cry::mrgreen:

目前评论:1   其中:访客  1   博主  0

    • avatar 访客

      来看看学习一下