一、概念及其介紹

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

創(chuàng)新互聯(lián)建站主要從事成都網(wǎng)站建設(shè)、做網(wǎng)站、網(wǎng)頁設(shè)計(jì)、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)紫陽,10多年網(wǎng)站建設(shè)經(jīng)驗(yàn),價(jià)格優(yōu)惠、服務(wù)專業(yè),歡迎來電咨詢建站服務(wù):13518219792二、適用說明

當(dāng)有 n 個(gè)記錄時(shí)，需進(jìn)行 logn 輪歸并排序，每一輪歸并，其比較次數(shù)不超過 n，元素移動(dòng)次數(shù)都是 n，因此，歸并排序的時(shí)間復(fù)雜度為 O(nlogn)。歸并排序時(shí)需要和待排序記錄個(gè)數(shù)相等的存儲(chǔ)空間，所以空間復(fù)雜度為 O(n)。

歸并排序適用于數(shù)據(jù)量大，并且對(duì)穩(wěn)定性有要求的場(chǎng)景。

三、過程圖示

歸并排序是遞歸算法的一個(gè)實(shí)例，這個(gè)算法中基本的操作是合并兩個(gè)已排序的數(shù)組，取兩個(gè)輸入數(shù)組 A 和 B，一個(gè)輸出數(shù)組 C，以及三個(gè)計(jì)數(shù)器 i、j、k，它們初始位置置于對(duì)應(yīng)數(shù)組的開始端。

A[i] 和 B[j] 中較小者拷貝到 C 中的下一個(gè)位置，相關(guān)計(jì)數(shù)器向前推進(jìn)一步。

當(dāng)兩個(gè)輸入數(shù)組有一個(gè)用完時(shí)候，則將另外一個(gè)數(shù)組中剩余部分拷貝到 C 中。

自頂向下的歸并排序，遞歸分組圖示：

對(duì)第三行兩個(gè)一組的數(shù)據(jù)進(jìn)行歸并排序

對(duì)第二行四個(gè)一組的數(shù)據(jù)進(jìn)行歸并排序

整體進(jìn)行歸并排序

四、參考代碼

public class MergeSort {

    // 將arr[l...mid]和arr[mid+1...r]兩部分進(jìn)行歸并
    private static void merge(Comparable[] arr, int l, int mid, int r) {

        Comparable[] aux = Arrays.copyOfRange(arr, l, r + 1);

        // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
        int i = l, j = mid + 1;
        for (int k = l; k<= r; k++) {

            if (i >mid) {  // 如果左半部分元素已經(jīng)全部處理完畢
                arr[k] = aux[j - l];
                j++;
            } else if (j >r) {   // 如果右半部分元素已經(jīng)全部處理完畢
                arr[k] = aux[i - l];
                i++;
            } else if (aux[i - l].compareTo(aux[j - l])< 0) {  // 左半部分所指元素< 右半部分所指元素
                arr[k] = aux[i - l];
                i++;
            } else {  // 左半部分所指元素 >= 右半部分所指元素
                arr[k] = aux[j - l];
                j++;
            }
        }
    }

    // 遞歸使用歸并排序,對(duì)arr[l...r]的范圍進(jìn)行排序
    private static void sort(Comparable[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = (l + r) / 2;
        sort(arr, l, mid);
        sort(arr, mid + 1, r);
        // 對(duì)于arr[mid]<= arr[mid+1]的情況,不進(jìn)行merge
        // 對(duì)于近乎有序的數(shù)組非常有效,但是對(duì)于一般情況,有一定的性能損失
        if (arr[mid].compareTo(arr[mid + 1]) >0)
            merge(arr, l, mid, r);
    }

    public static void sort(Comparable[] arr) {

        int n = arr.length;
        sort(arr, 0, n - 1);
    }

    // 測(cè)試MergeSort
    public static void main(String[] args) {

        int N = 1000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        sort(arr);
        //打印數(shù)組
        SortTestHelper.printArray(arr);
    }
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

文章名稱：JAVA編程----歸并排序-創(chuàng)新互聯(lián)
標(biāo)題鏈接：http://www.rwnh.cn/article32/dhhepc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供靜態(tài)網(wǎng)站、云服務(wù)器、服務(wù)器托管、網(wǎng)站制作、品牌網(wǎng)站建設(shè)、用戶體驗(yàn)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)