歸并排序（Merge Sort）

1、概述

歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。将已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若将兩個有序表合并成一個有序表，稱為二路歸并。

歸并過程為：比較a[i]和a[j]的大小，若a[i]≤a[j]，則将第一個有序表中的元素a[i]複制到r[k]中，并令i和k分别加上1；否則将第二個有序表中的元素a[j]複制到r[k]中，并令j和k分别加上1，如此循環下去，直到其中一個有序表取完，然後再将另一個有序表中剩餘的元素複制到r中從下标k到下标t的單元。歸并排序的算法我們通常用遞歸實作，先把待排序區間[s,t]以中點二分，接着把左邊子區間排序，再把右邊子區間排序，最後把左區間和右區間用一次歸并操作合并成有序的區間[s,t]。

2、算法原理

歸并操作的工作原理如下：

1. 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并後的序列

2. 設定兩個指針，最初位置分别為兩個已經排序序列的起始位置

3. 比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置

4. 重複步驟3直到某一指針超出序列尾将另一序列剩下的所有元素直接複制到合并序列尾

又如：

将序列每相鄰兩個數字進行歸并操作（merge)，形成floor(n/2)個序列，排序後每個序列包含兩個元素。将上述序列再次歸并，形成floor(n/4)個序列，每個序列包含四個元素。重複步驟2，直到所有元素排序完畢。

3、算法分析

①時間複雜度

時間複雜度為O(nlogn)這是該算法中最好、最壞和平均的時間性能。

空間複雜度為 O(n)。

比較操作的次數介于(nlogn) / 2和nlogn - n + 1。

指派操作的次數是(2nlogn)。歸并算法的空間複雜度為：0(n)。

歸并排序比較占用記憶體，但卻是一種效率高且穩定的算法。

②算法穩定性

歸并排序是穩定的排序。

即相等的元素的順序不會改變。

如輸入記錄：

1(1)、3(2)、2(3)、2(4)、5(5) (括号中是記錄的關鍵字)時輸出的

1(1)、2(3)、2(4)、3(2)、5(5)中的2和2是按輸入的順序。

這對要排序資料包含多個資訊而要按其中的某一個資訊排序，要求其它資訊盡量按輸入的順序排列時很重要，這也是它比快速排序優勢的地方。

4、算法執行個體

代碼如下：

/**
 * @author Hanlin Wang
 */

public class MergeSort {
    public static void main(String[] args) {
        //建立資料
        int[] data = {,,,};

        //進行歸并排序
        sort(data);

        //排序後，列印結果
        String txt = "";
        for (int i : data) {
            txt += i + ",";
        }
        String res = txt.substring(, txt.length()-);
        System.out.println(res);
    }

    //歸并排序的入口
    public static void sort(int[] data){
        mergeSort(data, , data.length - );
    }

    //歸并排序
    public static void mergeSort(int[] data, int low, int high){
        //若low<high，說明可以再分
        if (low<high) {
            int center = (low+high)/;
            mergeSort(data, low, center);
            mergeSort(data, center+, high);

            merge(data, low, center, high);
        }
    }

    //歸并這一步驟
    public static void merge(int[] data, int low, int center, int high){
        //建立臨時數組以後返還給data
        int[] tmpArr = new int[data.length];

        //臨時數組的角标
        int index = low;

        //第二部分的起始位
        int mid = center+;

        //供以後将臨時數組的值賦給data數組做初始化的臨時角标
        int tmp = low;

        //當切僅當low小于center，mid小于high進入循環
        while (low<=center&&mid<=high) {
            //如果目前角标的low的值小于mid值，将low角标值指派給tmpArr，并同時将角标+1
            if (data[low]<=data[mid]) {
                tmpArr[index++] = data[low++];
            } else {
                tmpArr[index++] = data[mid++];
            }
        }

        //處理剩餘的值。事實上，隻會進入其中的一個循環
        while (low<=center) {
            tmpArr[index++] = data[low++];
        }

        while (mid<=high) {
            tmpArr[index++] = data[mid++];
        }

        //将tmpArr的值塞入data中，完成合并
        while (tmp<=high) {
            data[tmp] = tmpArr[tmp++];
        }
    }
}
           

運作結果：

1,2,3,4

轉載于:https://www.cnblogs.com/wanxi/p/6476205.html