快捷導(dǎo)航

JAVA十大排序算法之歸并排序詳解

更新時(shí)間：2021年08月23日 09:56:43 作者：阿粵Ayue

這篇文章主要介紹了java中的歸并排序，本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下

歸并排序

歸并，指合并，合在一起。歸并排序（Merge Sort）是建立在歸并操作上的一種排序算法。其主要思想是分而治之。什么是分而治之？分而治之就是將一個(gè)復(fù)雜的計(jì)算，按照設(shè)定的閾值進(jìn)行分解成多個(gè)計(jì)算，然后將各個(gè)計(jì)算結(jié)果進(jìn)行匯總。即“分”就是把一個(gè)大的通過遞歸拆成若干個(gè)小的，“治”就是將分后的結(jié)果在合在一起。

若將兩個(gè)有序集合并成一個(gè)有序表，稱為2-路歸并，與之對(duì)應(yīng)的還有多路歸并。

怎么分

對(duì)于排序最好的情況來(lái)講，就是只有兩個(gè)元素，這時(shí)候比較大小就很簡(jiǎn)單，但是還是需要比較
如果拆分為左右各一個(gè)，無(wú)需比較即是有序的。

怎么治

借助一個(gè)輔助空數(shù)組，把左右兩邊的數(shù)組按照大小比較，按順序放入輔助數(shù)組中即可。

以下面兩個(gè)有序數(shù)組為例：

歸并排序

代碼實(shí)現(xiàn)

public class MergeSort {
    public static final int[] ARRAY = {8, 5, 6, 4, 3, 1, 7, 2};
    public static int[] sort(int[] array) {
        if (array.length < 2) return array;
        int mid = array.length / 2;
        //分成2組
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);
        //遞歸拆分
        return merge(sort(left), sort(right));
    }
    //治---合并
    public static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        //i代表左邊數(shù)組的索引，j代表右邊
        for (int index = 0, i = 0, j = 0; index < result.length; index++) {
            if (i >= left.length) {//說(shuō)明左側(cè)的數(shù)據(jù)已經(jīng)全部取完，取右邊的數(shù)據(jù)
                result[index] = right[j++];
            } else if (j >= right.length) {//說(shuō)明右側(cè)的數(shù)據(jù)已經(jīng)全部取完，取左邊的數(shù)據(jù)
                result[index] = left[i++];
            } else if (left[i] > right[j]) {//左邊大于右邊，取右邊的
                int a = right[j++];
                result[index] = a;
            } else {//右邊大于左邊，取左邊的
                result[index] = left[i++];
            }
        }
        return result;
    }
    public static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + "  ");
        }
        System.out.println("");
    }
    public static void main(String[] args) {
        print(ARRAY);
        System.out.println("============================================");
        print(sort(ARRAY));
    }
}

時(shí)間復(fù)雜度

歸并排序方法就是把一組n個(gè)數(shù)的序列，折半分為兩個(gè)序列，然后再將這兩個(gè)序列再分，一直分下去，直到分為n個(gè)長(zhǎng)度為1的序列。然后兩兩按大小歸并。如此反復(fù)，直到最后形成包含n個(gè)數(shù)的一個(gè)數(shù)組。

歸并排序總時(shí)間 = 分解時(shí)間 + 子序列排好序時(shí)間 + 合并時(shí)間

無(wú)論每個(gè)序列有多少數(shù)都是折中分解，所以分解時(shí)間是個(gè)常數(shù)，可以忽略不計(jì)，則：

歸并排序總時(shí)間 = 子序列排好序時(shí)間 + 合并時(shí)間

假設(shè)處理的數(shù)據(jù)規(guī)模大小為 n，運(yùn)行時(shí)間設(shè)為：T(n)，則T(n) = n，當(dāng) n = 1時(shí)，T(1) = 1

由于在合并時(shí)，兩個(gè)子序列已經(jīng)排好序，所以在合并的時(shí)候只需要 if 判斷即可，所以n個(gè)數(shù)比較，合并的時(shí)間復(fù)雜度為 n。

將 n 個(gè)數(shù)的序列，分為兩個(gè) n/2 的序列，則：T(n) = 2T(n/2) + n
將 n/2 個(gè)數(shù)的序列，分為四個(gè) n/4 的序列，則：T(n) = 4T(n/4) + 2n
將 n/4 個(gè)數(shù)的序列，分為八個(gè) n/8 的序列，則：T(n) = 8T(n/8) + 3n
…
將 n/2k 個(gè)數(shù)的序列，分為2k個(gè) n/2k 的序列，則：T(n) = 2kT(n/2k) + kn

當(dāng) T(n/2k) = T(1)時(shí)，即n/2k = 1（此時(shí)也是把n分解到只有1個(gè)數(shù)據(jù)的時(shí)候），轉(zhuǎn)換為以2為底n的對(duì)數(shù)：k = log2n，把k帶入到T(n)中，得：T(n) = n + nlog2n。

使用大O表示法，去掉常數(shù)項(xiàng) n，省略底數(shù) 2，則歸并排序的時(shí)間復(fù)雜度為：O(nlogn)