歸并排序

一、優先級佇列 堆 PriorityQueue

二、深入了解快排 以及 優化

歸并排序在八大排序中常考的次數，可以說是名列前茅，地位也是很高的不容疏忽，在排序中快速排序，歸并排序和堆排序，面試官基本都會問其中之一的排序，時間復雜度也是在排序中是最快的，所以必須掌握，有了前面快排的知識（快速排序 ）和堆排序知識（堆排序），歸并理解起來，也不會太抽象

🍕🍔🍟歸并排序：

歸并排序（Merge Sort）是建立在歸并操作上的一種有效，穩定的排序演算法，該演算法是采用分治法（Divide and Conquer）的一個非常典型的應用，將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序，若將兩個有序表合并成一個有序表，稱為二路歸并，

🚗🚓🚕基本思想：

歸并排序的思想其實很簡單，是采用分治的思想，定義一個mid，從而分開左邊和右邊，每一次像二叉樹一樣遞回，，讓他分成一個一個的數然后最后在合并排序，

一、合并兩個有序陣列

要想完成歸并排序，首先要知道怎么讓兩個有序陣列合并有序成一個陣列，這也是歸并排序的核心思想

首先有兩個有序的陣列，定義start和end，兩個陣列s1和s2進行比較，小的就放進tmp陣列中，k是tmp陣列的下標（index），

走到這一步了，s2已經走完了，s1剩下的就直接放下去就行了，

🍰🎂🍪核心代碼：代碼還是很簡單的😁😁😁😁

public static int[] mergeArray(int[] array1,int[] array2) {
        int[] tmp = new int[array1.length+array2.length];//新陣列的長度是array1和array2相加的長度
        int k = 0;//tmp陣列的下標

        int s1 = 0;
        int e1 = array1.length-1;//可以不寫

        int s2 = 0;
        int e2 = array2.length-1;//可以不寫

        //兩個陣列比較
        while (s1 <= e1 && s2 <= e2) {
            if(array1[s1] <= array2[s2]) {
                tmp[k++] = array1[s1++];
            }else {
                tmp[k++] = array2[s2++];
            }
        }
        //把剩下的直接放進tmp陣列
        while (s1 <= e1) {
            tmp[k++] = array1[s1++];
        }
        while (s2 <= e2) {
            tmp[k++] = array2[s2++];
        }
        return tmp;
    }

現在我們核心思想代碼寫完了，那么歸并排序就只剩下框架了，這次我們用遞回思想；

二、遞回版本

這里要注意的點是分的時候，左邊是以mid結尾，右邊是mid+1結尾

代碼：

//待排序區間
    public static void mergeSortInternal(int[] array,int left,int right) {
        if(left>=right) {//終止條件
            return;
        }

        int mid=(left+right)/2;
        mergeSortInternal(array,left,mid);
        mergeSortInternal(array,mid+1,right);
    }

上面鋪墊的差不多的了，把上面的代碼應用起來就可以了，

完整代碼：

public static void merge(int[] array,int left,int right,int mid) {
        int[] tmp=new int[right=left+1];
        int k=0;

    //開始分治，mid是左邊結尾
        int s1=left;
        int e1=mid;

    //mid+1是右邊的開始
        int s2=mid+1;
        int e2=right;

        while (s1<=e1 && s2<=e2) {
            if(array[s1]<=array[s2]) {
                tmp[k++]=array[s1++];
            } else {
                tmp[k++]=array[s2++];
            }
        }

        while (s1<=e1) {
            tmp[k++]=array[s1++];
        }
        while (s2<=e2) {
            tmp[k++]=array[s2++];
        }

        for (int i = 0; i < k; i++) {
            array[i+left]=tmp[i];//！！！！！！！！
            //這里要注意了，不能寫成array[i]=tmp[i],因為分右邊的時候，是mid+1下標結尾的，
        }
    }
    //待排序區間
    public static void mergeSortInternal(int[] array,int left,int right) {
        if(left>=right) {//終止條件
            return;
        }

        int mid=(left+right)/2;
        mergeSortInternal(array,left,mid);
        mergeSortInternal(array,mid+1,right);
        merge(array,left,right,mid);
    }

    public static void mergeSort(int[] array) {
        mergeSortInternal(array,0,array.length-1);
    }

這里有個要注意的點：

在把tmp里面的陣列放進array里面的陣列時，一定要寫成 array[i+left]=tmp[i];

如果寫成array[i]=tmp[i]，就會把原陣列里面的陣列覆寫掉，

三、性能分析

時間復雜度相當于二叉樹高度+遍歷，空間復雜度因為有new tmp所以是O（n).

四、非遞回版本

非遞回版本理解起來就麻煩了，因為會考慮很多種情況，還要注意很多邊界的問題，實屬心煩，如果要寫歸并排序還是直接寫遞回的好，如果有要求那就，只能硬著頭皮干了🐱?👤🐱?👤🐱?👤🐱?👤🐱?👤🐱?👤🐱?👤🐱?👤🐱?👤🐱?👤

首先要歸并是必須要兩個陣列的，但是每個陣列會分gap，先是1組，然后2組，然后4組，跟上面圖差不多的分組，

😎🙂🤗分組代碼：

public static void mergeSort(int[] array) {
        for (int gap = 1; gap < array.length; gap*=2) {
            merge2(array,gap);
        }
    }

由圖所示，這樣就可以確定 s1,e1,s2,e2的位置了，但是e2可能要稍微注意：

所以當e2大于陣列長度的時候，直接len-1，

😶😑😐位置代碼：

public static void merge2(int[] array,int gap) {

        int[] tmp = new int[array.length];
        int k = 0;
        int s1 = 0;
        int e1 = s1+gap-1;
        int s2 = e1+1;
        int e2 = s2+gap-1 >= array.length ? array.length-1 : s2+gap-1;
}

下面就是兩個陣列的比較了，兩個陣列就必須有兩個段，所以會有一個判斷條件兩陣列比較也寫過直接拿來用

代碼：

 while (s2 < array.length) {//這是判斷必須有兩個段的判斷條件
            while (s1 <= e1 && s2 <= e2) {
                if (array[s1] <= array[s2]) {
                    tmp[k++] = array[s1++];
                }else {
                    tmp[k++] = array[s2++];
                }
            }
            while ( s1 <= e1 ) {
                tmp[k++] = array[s1++];
            }
            while (s2 <= e2) {
                tmp[k++] = array[s2++];
            }
        }

因為不是遞回，所以兩段陣列比完了，還要確定下一次兩段陣列的位置所以就要接著寫：

s1 = e2+1;
e1 = s1+gap-1;
s2 = e1+1;
e2 = s2+gap-1 >= array.length ? array.length-1 : s2+gap-1;

但是寫了上面的代碼會發生幾種情況：

會出現以上兩種情況，最后把多余的移下去，歸根結底，最后的取值范圍就是len-1；

完整代碼：

 public static void merge2(int[] array,int gap) {
        int[] tmp = new int[array.length];
        int k = 0;

        int s1 = 0;
        int e1 = s1+gap-1;
        int s2 = e1+1;
        int e2 = s2+gap-1 >= array.length ? array.length-1 : s2+gap-1;
        //一定要有2個段 ，拿s2判斷
        while (s2 < array.length) {

            while (s1 <= e1 && s2 <= e2) {
                if (array[s1] <= array[s2]) {
                    tmp[k++] = array[s1++];
                }else {
                    tmp[k++] = array[s2++];
                }
            }

            while ( s1 <= e1 ) {
                tmp[k++] = array[s1++];
            }
            while (s2 <= e2) {
                tmp[k++] = array[s2++];
            }

            s1 = e2+1;
            e1 = s1+gap-1;
            s2 = e1+1;
            e2 = s2+gap-1 >= array.length ? array.length-1 : s2+gap-1;

        }

        //只剩下最后段了，綜合考慮會出現多重情況，歸根結底取值范圍就是len-1
        while (s1 <= array.length-1) {
            //s1 <= e1還要考慮的情況是   存在s1但是不存在e1情況下， s1 <= array.length-1
            tmp[k++] = array[s1++];
        }
        for (int i = 0; i < k; i++) {
            array[i] = tmp[i];
        }
    }

 public static void mergeSort1(int[] array) {

        for (int gap = 1; gap < array.length; gap*=2) {
            merge2(array,gap);
        }
    }

以上就是這篇帖子的全部內容了，必須全掌握，在七大排序中，快排，堆排和歸并都是常考的內容，快排出現的次數最多的，其次就是堆和歸并，再后就是直接插入，希爾，選擇，冒泡 ，這些相對來說代碼和思想要簡單點，希爾排序有點難理解，但是幾乎不考，主要還是要熟知他們的時間復雜度，空間復雜度，穩定些，還有他們的主要實作都要掌握， 總結了歸并排序的代碼， 若想看全代碼可以 點擊我的 Github ，里面都是整理的代碼，

鐵汁們，覺得筆者寫的不錯的可以點個贊喲?🧡💛💚💙💜🤎🖤🤍💟，收藏關注唄，你們支持就是我寫博客最大的動力