圖解Java經(jīng)典算法歸并排序的原理與實(shí)現(xiàn)

更新時(shí)間：2022年09月09日 10:49:43 作者：Binaire-沐辰

歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide?and?Conquer）的一個(gè)非常典型的應(yīng)用。本文將通過(guò)動(dòng)圖詳解歸并排序的原理及實(shí)現(xiàn)，需要的可以參考一下

歸并排序

歸并排序主要分成兩部分實(shí)現(xiàn)，分、合兩部分，分是把數(shù)組分成兩半，再遞歸的對(duì)子數(shù)組進(jìn)行分操作，直到分成一個(gè)個(gè)單獨(dú)的數(shù)。合是把兩個(gè)數(shù)組合并為有序數(shù)組，在對(duì)有序數(shù)組進(jìn)行合并，直到全部子數(shù)組合并為一個(gè)完整的數(shù)組。

算法原理

申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來(lái)存放合并后的序列
設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
比較兩個(gè)指針?biāo)赶虻脑兀x擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置
重復(fù)步驟c直到某一指針超出序列尾
將另一序列剩下的所有元素直接復(fù)制到合并序列尾

動(dòng)圖演示

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

public class MergeSort {
    //歸并所需的輔助數(shù)組
    private static Comparable[] assist;
    //比較 v 是否小于 w
    public static boolean less(Comparable v,Comparable w){
        return v.compareTo(w) < 0;
    }
    //數(shù)組元素交換位置
    private static void swap(Comparable[] a,int i,int j){
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    //排序
    public static void sort(Comparable[] a){
        //初始化輔助數(shù)組
        assist = new Comparable[a.length];
        int l = 0;
        int h = a.length - 1;
        sort(a,l,h);
    }
    private static void sort(Comparable[] a,int l,int h){
        if (h <= l){
            return;
        }
        //分組
        int mid = l +(h - l) / 2;
        //分別對(duì)每組數(shù)據(jù)排序
        sort(a,l,mid);
        sort(a,mid + 1,h);
        //對(duì)數(shù)組進(jìn)行歸并
        merge(a,l,mid,h);
    }
    //對(duì)數(shù)組進(jìn)行歸并
    private static void merge(Comparable[] a,int l,int mid,int h){
        //定義三個(gè)指針
        int i = l;
        int p1 = l;
        int p2 = mid + 1;
        //遍歷，移動(dòng)p1,p2指針，比較兩處索引的值,小的放到輔助數(shù)組的對(duì)應(yīng)索引處
        while (p1 <= mid && p2 <=h){
            if (less(a[p1],a[p2])){
                assist[i++] = a[p1++];
            }else {
                assist[i++] = a[p2++];
            }
        }
        //遍歷數(shù)組，如果p1的指針沒(méi)有走完，則順序移動(dòng)p1指針，把對(duì)應(yīng)的元素放到輔助數(shù)組的對(duì)應(yīng)索引處
        while (p1 <= mid){
            assist[i++] = a[p1++];
        }
        //遍歷數(shù)組，如果p2的指針沒(méi)有走完，則順序移動(dòng)p2指針，把對(duì)應(yīng)的元素放到輔助數(shù)組的對(duì)應(yīng)索引處
        while (p2 <= h){
            assist[i++] = a[p2++];
        }
        //把輔助數(shù)組中的元素拷貝到原數(shù)組中
        for (int j = l; j <= h; j++) {
            a[j] = assist[j];
        }
    }
}

public class MergeSortTest {
    public static void main(String[] args) {
        Integer[] arr = {5,6,3,1,8,7,2,4};
        MergeSort.sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
//排序前：{5,6,3,1,8,7,2,4}
//排序后：{1,2,3,4,5,6,7,8}