排序算法-归并排序

前言：排序是现在程序员的必备技能，是很多公司的面试必考点，不管是做移动端，后端开发，排序是绕不过的，众生平等。学习其排序的思想往往能解决不同类型的问题，所以静下心来，研究一下不同的排序算法，算是对自己有一个提升。

排序概述：排序就是将一组对象按照某种逻辑顺序重新排列的过程。

十大排序算法：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序，希尔排序，计数排序，基数排序，桶排序。

本文对归并排序走一个解析：

归并排序步骤：

1.归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。

2.对于给定一组数据，利用递归与分治技术将数据序列划分成为越来越小的半子表，在对半子表排序后，再利用递归方法将排序好的半子表合并成为越来越大的有序序列。

3.为了提升性能，有时候我们在半子表的个数小于某个数（比如15的情况下），对半子表的排序采用其他排序算法，比如插入排序。

4.若将两个有序表合并成一个有序表，称为2-路归并，与之对应的还有多路归并。

代码举例：

对一个数组进行排序：（86,11,77,23,32,45,58,63,93,4,37,22）

int[] array = {86,11,77,23,32,45,58,63,93,4,37,22};

排序代码展示： 

归并排序

调用sort方法后打印如下：

归并排序打印

 对该案例进行分析：（86,11,77,23,32,45,58,63,93,4,37,22）

  进行第一次拆分  left :  [86, 11, 77, 23, 32, 45]---拆分-->right:   [58, 63, 93, 4, 37, 22] 

  注：根据此处代码执行递归顺序，每次都是先执行完左边子表，再进行右边子表拆分，所以这里只分析大左子表，逻辑是一样的

  左边大子表第一次拆分 ：[86, 11, 77]---拆分-->[23, 32, 45]

  （1）对于：[86, 11, 77]

             [86]---拆分-->[11, 77]

            [11]---拆分-->[77]

            执行完merge以后:

                     返回1：[11, 77]

                     返回2：[11, 77, 86]

 （2）对于：[23, 32, 45]

            [23]---拆分-->[32, 45]

            [32]---拆分-->[45] 

           执行完merge以后:

                      返回3：[32, 45]

                      返回4：[23，32，45]

根据递归顺序：

（3）返回2和返回4进行归并：[11, 23, 32, 45, 77, 86]

（4）右边大子表步骤和上面步骤一样：[4, 22, 37, 58, 63, 93]

（5）最后进行总合并 ：[4, 11, 22, 23, 32, 37, 45, 58, 63, 77, 86, 93]

至此排序结束

 打印每个步骤的数组：

归并排序

 

 至此归并排序就到这里讲解结束了，细看的话其实一点也不复杂。