歸并排序

前言

本篇文章是排序算法系列的第四篇，學習歸并排序

后面這段話將作為排序算法系列博客每一篇的開頭：

為避免文中過多贅述，寫在最前面：

1. 接下來所有的排序算法講解中，無論是思路梳理，還是代碼實現，都是最終實現從小到大排序，從大到小可以學會后自行類推。
2. 都是使用int數組進行排序，數據總量為n

歸并排序

核心理念

歸并排序核心思想是分治，分治法顧名思義，分開來治理，首先將一個大問題拆分成小問題，小問題逐個治理解決，最終再合起來完整的解決大問題

這里就直接說了，將一整個數組排序的問題，歸并排序的思想是拆分成兩個有序數組的合并問題。

我當初看到這里就馬上暫停了一下，自己去想，怎么才能把一個數組排序問題，拆分成兩個有序數組的合并，想了很久也沒想到，感覺怎么拆也不能保證都是有序的，接著往下看了，然后暈倒！當持續(xù)的拆下去，拆成左右兩個數組都只剩一個數據，一個數據當然是有序的，它們就全是有序的了......

到這里一下就豁然開朗了，先一步步拆到最底層再退回來合成到最頂層，思路就來了，首先將數組一分為二，此時的左右兩邊數組還不是有序的，我們要把他們都變成有序的，再重新將兩個數組當做新數組繼續(xù)一分為二，直到數組中只有一個數字為止，再分別將兩個一個數據的數組合成一個兩個數據的有序數組，再將兩個兩個數據的有序數組合成一個四個數據的有序數組，一直到合成回頂層。

實現思路

每一次拆分其實都是四個步驟：

1. 判斷當前數組長度是否大于1，不大于1就結束
2. 大于1就將數組對半拆成左右兩個數組
3. 左右數組也從第一步開始執(zhí)行這四個步驟
4. 將左右數組執(zhí)行有序數組合并（此時的左右數組，因為第三步的存在，一層一層進去又出來，已經是有序的了）

到這里，分治中，分的過程就通過遞歸達成了目的，但這個第四步還需要進一步去深入一下，將有兩個序數組合并成一個有序數組，步驟如下：

1. 準備一個長度是兩數組長度和的數組，臨時存放合并后的結果，用一個指針執(zhí)行數組第一個位置；
2. 用兩個指針分別指向兩個數組的第一個元素；
3. 如果兩個指針都沒有越界就進入循環(huán)，比較兩個指針處數據的大小，將小的一個放入臨時數組的指針位置，臨時數組指針后移，小的一個指針后移，然后再次判斷是否兩個指針都沒有越界，進入下一次循環(huán)
4. 直到其中一個指針越界了，說明其中一個有序數組全部放到臨時數組中了，因為兩個數組都是從小到大排列的有序數組，此時只需要將另一個數組中所有剩余的元素依次添加到臨時數組中即可
5. 完成上述四步，臨時數組中就是合并后的結果，將它存回原來拆開的兩個數組中就完成了一次合并

思路有了，大家可以試著自己寫完再來看代碼：

package com.zwx.sort;

/**
 * 歸并排序
 *
 * @author coderZWX
 * @date 2022-06-13 16:37
 */
public class MergeSort {

    public static void mergeSort(int[] arr){
        //由于最后一次合并，需要的臨時數組長度就是原數組的總長度，所以直接只創(chuàng)建一個最大的數組作為臨時數組全程使用
        MergeSort.mergeSort(arr,0,arr.length-1,new int[arr.length]);
    }

    private static void mergeSort(int[] arr, int start, int end, int[] temp){
        //如果數組段中的數據大于等于2個，就分割成左右兩邊
        if (start < end){
            //中間數索引（左邊的終點）
            int mid = (start + end) / 2;
            mergeSort(arr, start, mid, temp);
            mergeSort(arr, mid + 1, end, temp);
            //無論是否需要再次分割，分割完畢或不分割，都執(zhí)行一次合并操作
            merge(arr,start,mid,end,temp);
        }
    }

    /**
     * 將一個數組段，按(start+end)/2為左邊終點索引，分開為左右兩個數組，已知左右兩邊分別有序（從小到大），合并為全部有序（從小到大）
     * @param arr 大數組
     * @param start 起點索引
     * @param end 終點索引
     * @param temp 臨時數組
     */
    private static void merge(int[] arr, int start, int mid, int end, int[] temp) {
        //左起點為start，左終點為mid，右起點為mid+1，右終點為end
        //左指針
        int lPointer = start;
        //右指針
        int rPointer = mid + 1;
        //臨時數組指針
        int t = 0;
        //當左右指針都沒越界比較左右兩個指針指向數據的大小，誰小就把誰放在臨時數組指針位置，并將指針后移一個
        while (lPointer<= mid && rPointer<= end){
            if (arr[lPointer]<arr[rPointer]) {
                temp[t++] = arr[lPointer++];
            }else {
                temp[t++] = arr[rPointer++];
            }
        }
        //當某個指針沒越界，剩余的都放入臨時數組
        while (lPointer<= mid){
            temp[t++] = arr[lPointer++];
        }
        while (rPointer<= end){
            temp[t++] = arr[rPointer++];
        }
        //將排好序的temp放回arr的start到end
        int index = start;
        t = 0;
        while (index<=end){
            arr[index++] = temp[t++];
        }
    }
}

測試對比

寫這篇文章的時候，和之前三篇不在同一個電腦環(huán)境測試，但我們知道之前篇章中，最快的是快速排序，這里先運行了最快的交換法快速排序，隨機散列的800w數據排序，大約1100ms左右，這里的歸并排序在1300ms左右，還是路遜與快速排序

但是在選擇排序算法的時候，并不能無腦快速排序，各個排序都有優(yōu)缺點，日常中有排序需求的時候，800w隨機分散在0-8000w整數的非常散列的數據排序是很少見的，重點是理解這些排序的思想，擴寬思路，真正排序還需要具體情況具體分析。

jdk源碼中，Arrays.sort()方法，也使用到了歸并排序，但暫時不去看，后續(xù)介紹完其他排序算法，再來開章節(jié)閱讀jdk源碼中的排序