java歸并排序算法的原理和作用

這篇文章主要介紹“java歸并排序算法的原理和作用”，在日常操作中，相信很多人在java歸并排序算法的原理和作用問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”java歸并排序算法的原理和作用”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

1、定義

    歸并排序是一種概念上最簡單的排序算法，與快速排序一樣，歸并排序也是基于分治法的。歸并排序將待排序的元素序列分
成兩個長度相等的子序列，為每一個子序列排序，然后再將他們合并成一個子序列。合并兩個子序列的過程也就是兩路歸并。

圖解（摘自網絡）

2、代碼

public class TestController {

    public static void main(String[] args) {
        int[] a = { 49, 38, 65, 97, 76, 13, 27, 50 };
        mergeSort(a, 0, a.length-1);
        System.out.println("排好序的數組：" + Arrays.toString(a));

    }
    public static void mergeSort(int [] a,int start,int end){

        // 當子序列中只有一個元素時結束遞歸
        if(start<end){
            // 劃分子序列
            int mid=(start+end)/2;

            // 對左側子序列進行遞歸排序
            mergeSort(a, start, mid);

            // 對右側子序列進行遞歸排序
            mergeSort(a, mid+1, end);

            // 合并
            merge(a, start, mid, end);
        }
    }

    //兩路歸并算法，兩個排好序的子序列合并為一個子序列
    public static void merge(int []a,int left,int mid,int right){
        // 輔助數組
        int []tmp=new int[a.length];

        // p1、p2是檢測指針，k是存放指針
        int p1=left,p2=mid+1,k=left;

        while(p1<=mid && p2<=right){
            if(a[p1]<=a[p2])
                tmp[k++]=a[p1++];
            else
                tmp[k++]=a[p2++];
        }

        // 如果第一個序列未檢測完，直接將后面所有元素加到合并的序列中
        while(p1<=mid) {
            tmp[k++]=a[p1++];
        }
        // 如果第一個序列未檢測完，直接將后面所有元素加到合并的序列中
        while(p2<=right) {
            tmp[k++]=a[p2++];
        }

        // 復制回原素組
        for (int i = left; i <=right; i++) {
            a[i]=tmp[i];
        }
    }
}

3、結果

排好序的數組：[13, 27, 38, 49, 50, 65, 76, 97]

到此，關于“java歸并排序算法的原理和作用”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！