快捷導(dǎo)航

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

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

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

歸并排序

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

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

怎么分

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

怎么治

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

以下面兩個有序數(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) {//說明左側(cè)的數(shù)據(jù)已經(jīng)全部取完，取右邊的數(shù)據(jù)
                result[index] = right[j++];
            } else if (j >= right.length) {//說明右側(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));
    }
}