八大排序（二）：归并排序

╰+攻爆jí腚メ 2022-05-25 02:39 156阅读 0赞

源码地址：  
[https://github.com/TimePickerWang/aimed-at-offer/blob/master/java%E6%BA%90%E7%A0%81/Sort.java][https_github.com_TimePickerWang_aimed-at-offer_blob_master_java_E6_BA_90_E7_A0_81_Sort.java]

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。分治法即将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，归并排序的速度仅次于快速排序，比较次数小于快速排序的比较次数，而移动次数一般多于快速排序的移动次数。

归并排序的过程可以结合下图来理解：  
![这里写图片描述][70]

其中，“治”阶段的过程如下图：  
![这里写图片描述][70 1]

一般归并排序的代码把“分”和“治”的操作分开了，以下的的代码把划分和合并合在一起，用空格隔开了。归并排序和之前[剑指offer-题36：数组中的逆序对][offer-_36]的思路相似。注意在mergeSortCore函数中再次递归调用mergeSortCore函数的传值：将array和tempArray的顺序调换了一下，原因可以这样理解：  
在最后一层递归调用后，tempArray会是排序完成的结果，而array是排序之前的结果。此时把结果返回给倒数第二层，注意，此时倒数第二层array对应最后一层的tempArray，而tempArray对应array，也就是说倒数第二层的array是上一层最新的排序好的结果，而tempArray是次新的结果。在倒数第二层经过后半段的排序后，此时的tempArray会成为最新排序好的结果返回倒数第三层的array，而array会作为次新的结果返回给倒数第三层的tempArray（可能把你绕晕了，可以画一个图方便理解）。根据这个规律，运行到递归最开始的那一层时，array是最新排序好的，在程序的后半段，再根据array的顺序进行最后一次归并，tempArray会成为最终排序的结果，因此最后返回的结果是tempArray。具体代码如下

归并排序：

public float[] mergeSort(float[] array) {
            float[] tempArray = new float[array.length];
            System.arraycopy(array, 0, tempArray , 0, array.length);
            mergeSortCore(array, tempArray, 0, array.length - 1);
            return tempArray;
        }
    
        // 归并排序
        public void mergeSortCore(float[] array, float[] tempArray, int start, int end) {
            if (start == end) {
                tempArray[start] = array[start];
                return;
            } else if (start < end) {
                int middle = (start + end) >> 1;
                mergeSortCore(tempArray, array, start, middle);
                mergeSortCore(tempArray, array, middle + 1, end);
    
                int i = start;
                int j = middle + 1;
                int k = start;
                while (i <= middle && j <= end) {
                    if (array[i] <= array[j]) {
                        tempArray[k++] = array[i++];
                    } else {
                        tempArray[k++] = array[j++];
                    }
                }
                while (i <= middle) {
                    tempArray[k++] = array[i++];
                }
                while (j <= end) {
                    tempArray[k++] = array[j++];
                }
            }
        }

ref:  
[图解排序算法(四)之归并排序][Link 1]

[https_github.com_TimePickerWang_aimed-at-offer_blob_master_java_E6_BA_90_E7_A0_81_Sort.java]: https://github.com/TimePickerWang/aimed-at-offer/blob/master/java%E6%BA%90%E7%A0%81/Sort.java
[70]: /images/20220525/258785de9e8f4fb3879ffa2fe69b2736.png
[70 1]: /images/20220525/3b4e0e70c24c4717a8281cae9effe6f3.png
[offer-_36]: https://blog.csdn.net/wang454592297/article/details/79855793
[Link 1]: https://www.cnblogs.com/chengxiao/p/6194356.html