十大排序算法:二路归并排序(难点为对于递归的理解)

归并排序(Merge Sort)算法思想:就是利用归并的思想实现排序的方法。

它的原理是假设初始序列有N个长度,则可以看成是N个有序的子序列,每个子序列的长度为1，然后两两归并,得到N/2个长度为2或1的有序子序列,再两两归并...如此重复,直至得到一个长度为N的有序序列为止,这种排序方法称为2路归并排序.

示例以及图片分析:

先将数组中的八个数全部分开成单个的八个数据(此时单个元素一定有序),再依次两两结合形成四对有序的数据组如图所示,再次两两结合形成两队有序的数据组(即为 4578 与 1236两个都是有序的数组),最后将这两个数组进行结合形成最终的有序数组.对于最后两队合成最终有序数组的过程为:

首先令4与1比较得最小数为1填入临时数组现有的第一个空格里面,之后再比较4与2得2为暂时的最小数据,按着前一个空格里面填入,不断继续比较,直到某个对里完全为空，将另一个对里面的数据按顺序全部填入临时数组即完成排序(例如7与6比完后直接将78填入了临时数组剩下的空中！)

代码如下:

  package paixu;
  import java.util.Arrays;
  public class diGuiSort {
      public static void main(String[] args) {
          //原始待排序数组(无序的)
          int[] arr={10,30,2,1,0,8,7,5,19,29};
          //我们先给一个左右两边是有序的一个数组先来进行归并操作
          //int[] arr={4,5,7,8,1,2,3,6};
          //拆分之后就是可以不断调用归并函数(对半分)
          chaifen(arr,0,arr.length-1);
          //归并
          //guiBing(arr,0,3,arr.length-1);
  
          //输出原数组
          System.out.println(Arrays.toString(arr));
      }
  
      private static void chaifen(int[] arr, int startIndex, int endIndex) {
          //要先算出中间索引
          int centerIndex=(startIndex endIndex)/2;
          if(startIndex<endIndex){
              chaifen(arr,startIndex,centerIndex);
              chaifen(arr,centerIndex 1,endIndex);
              guiBing(arr,startIndex,centerIndex,endIndex);
          }
      }
      private static void guiBing(int[] arr, int startIndex, int centerIndex, int endIndex) {
          //定义一个临时数组
          int[] tempArr = new int[endIndex-startIndex 1];
          //定义左边数组的起始索引
          int i=startIndex;
          //定义右边数组的起始索引
          int j=centerIndex 1;
          //定义临时数组的起始索引
          int index=0;
          //比较左右两个数组的元素大小,往临时数组中放
          while (i<=centerIndex&&j<=endIndex){
              if(arr[i]<=arr[j]){
                  tempArr[index]=arr[i];
                  i  ;
              }else{
                  tempArr[index]=arr[j];
                  j  ;
              }
              index  ;
          }
          //再处理剩余元素
          while(i<=centerIndex){//左边数组有剩余元素就算等于centerIndex也是还有最后一个数据
              tempArr[index]=arr[i];
              i  ;
              index  ;
          }//要注意的是两个数组不可能都有剩余
          while(j<=endIndex){//右边数组有剩余元素就算等于endIndex也是还有最后一个数据
              tempArr[index]=arr[j];
              j  ;
              index  ;
          }
          //System.out.println(Arrays.toString(tempArr));
          //将临时数组中的元素取到原数组中;
          for(int k=0;k<tempArr.length;k  ){
              arr[k startIndex]=tempArr[k];//临时数组是从0开始传递过来的原数组是从startIndex开始
          }
      }
  }

  
  首先对于方法guiBing(int[] arr, int startIndex, int centerIndex, int endIndex)为将确定的两个分组进行合并并且以合并后有序的顺序填入原数组中(借由中间数组),首先利用int[] tempArr = new int[endIndex-startIndex 1];定义一个对应两个分组之和大小的中间数组用来暂时存放排好序后的两个数组的序列,之所以用stratIndex,centerIndex,endIndex是因为调用时候分组大小是不确定的,所以用int型的形参来代替,之后按照上方自己所画图的方法进行循环比较,注意:循环判断条件为i<=centerIndex&&j<=endIndex即为每个分区只能在本分区内找数与另一分区的数进行比较,否则即为某分区内数已经找完(例如上方为由于j>endIdex的情况使循环退出),而循环内部的语句就是将找到的暂时最小的数不断由前向后填入临时数组的空格内,index=0就是用于不断填入临时数组(故而代码为判断arr[i]与arr[j]的大小若为arr[i]<=arr[j]则令arr[i]较小值填入tempArr[index];之后令i  (之后用左边数组的后面一个与j所代表的右边数组比较);与index  (令下次较小数填入临时数组的后方空格内),否则(>)则为将j代表元素填入tempArr[index]中并令j  ;index  ;)当此循环退出后即代表某个分区已经全部装入临时数组,有个分区仍未装入(至少还有一个元素且该分区仍为有序的,即大于临时数组中的所有数据,因此直接将其全部插入临时数组的末尾即可.)先看是否为左边元素未空,即while(i<=centerIndex)则不断将对应的arr[i]填入tempArr[index]中直到i>centerIndex为止,同理也要判断右边元素是否为空即while(j<=endIndex)同样的对右边剩余元素进行同样处理.此时已经两个分区排序完毕后全部装入临时数组,之后用for循环全部按顺序复制(赋值)到原数组arr中即可实现分区的合并并且能够体现在原数组中.
  之后的重点也就时难点就在于拆分方法的理解,对于最上方图片可以看出应该先进行拆分当拆分完成为均为一个的节点后便进行相邻两个同样大小分区的合并.此时涉及到递归的调用,用递归的方法，对于输入的一个初始数组,先调用 chaifen(arr,0,arr.length-1);进行拆分,而对于自己定义的chaifen方法则是先根据center递归调用表示将分成的两个分组也进行拆分即chaifen(arr,startIndex,centerIndex);与chaifen(arr,centerIndex 1,endIndex);之后就直接调用递归函数即可.实际理解可以根据对于某个实例的分析进行理解。具体如下图所示

理解如下对于其实长度为N的一个数组一定会因为递归的调用被逐渐分为大小为N/2的两个分区，N/4的四个分区....最终分为大小为1的N个分区,对于大小为一的分区也会调用cf(arr,num,num);但此时num=num;于是什么也不会执行,且由于为递归执行所在在所有的大小为1的分区为执行完之前都不会执行大小为2的分区,故而当执行大小为2的分区时就会执行guibing()函数也即是将大小为1的分区进行排序后合并放入原数组中,对于一个chaifen(arr,startIndex,endIndex)方法来说由函数体可得一定会执行其对应的guibing(arr,startIndex,centerIndex,endIndex)方法,故而会优先执行所有的大小为2的guibing方法(因为一旦有大小为4的方法想要执行一定会递归调用大小为2的chaifen方法)故而就实现了合并中从大小为1的分区逐渐两两合并最终合并为大小为N的有序数组，故而完成了此排序算法。

重难点：对于拆分过程的递归调用，从而实现先执行大小逐渐减小的拆分,再执行大小逐渐增大的合并,且对于合并来说当小的分区未完全合并之前,一定不会执行大的分区的合并，这就能实现第一个图片的思想.

这篇好文章是转载于：学新通技术网