[Day18] CH10：排序大家族——合并排序法

今天要介绍的是我们学的最後一个排序法——合并排序法（Merge Sort）。

合并排序法

分成切割与合并两个部分：

切割

将数列对分成左子数列、右子数列。分别对左子数列、右子数列做前一个步骤（递回 Recursive）。

直到左子数列、右子数列被分割成只剩一个元素为止，将仅剩的一个元素作为递回的结果回传，对回传的左子数列、右子数列依大小排列合并，将合并的结果作为递回的结果回传。
合并

将左子数列及右子数列依大小合并成一个新的数列（需执行 ⌈log 2n⌉ 回合）：
1. 若左子数列的数值都已填到新的数列，将右子数列中未填过的最小值填入新数列
2. 若右子数列的数值都已填到新的数列，将左子数列中未填过的最小值填入新数列
3. 将左子数列及右子数列中，未填过的最小值填到新的数列

给定一个阵列：

41, 24, 97,  6, 19, 53, 78

首先先将阵列拆成左子阵列与右子阵列

41, 24, 97,  6       19, 53, 78

持续递回将左子阵列与右子阵列继续切割，直到都只剩下一个数字

41, 24       97,  6       19, 53, 78

41, 24       97,  6       19, 53       78

41       24       97,  6       19, 53       78

41       24       97        6       19, 53       78

41       24       97        6       19       53       78

接下来将各阵列合并：最小值先填入

24, 41       97        6       19       53       78

24, 41        6, 97       19       53       78

24, 41        6, 97       19, 53       78

 6, 24, 41, 97       19, 53       78

 6, 24, 41, 97       19, 53, 78

 6, 19, 24, 41, 53, 78, 97

以上的范例大家可能有看没有懂，那就来看看动图和程序码吧：

合并排序法动图

public class MergeSort{
    public static void main(String[] args){
        int[] arr = {41, 24, 97, 6, 19, 53, 78};
        int n = arr.length;
        mergesort(arr, 0, n - 1);
        for(int i = 0 ; i < n ; i++){
            System.out.printf("%d ", arr[i]);
        }
    }

    public static void merge(int[] arr, int head, int mid, int tail){
        int lenA = mid - head + 1;
        int lenB = tail - (mid+1) + 1;
        int[] A = new int[lenA];    //左子数列
        int[] B = new int[lenB];    //右子数列
        int i,j;
        for(i = 0 ; i < lenA ; i++){
            A[i] = arr[head+i];
        }
        for(j = 0 ; j < lenB ; j++){
            B[j] = arr[mid+1+j];
        }
        i = 0;
        j = 0;
        int k = head;
        while(i < lenA && j < lenB){
            if(A[i] < B[j]){
                arr[k] = A[i];
                i++;
                k++;
            }
            else{
                arr[k] = B[j];
                j++;
                k++;
            }
        }
        //右子数列已经结束，将左子数列剩余的数复制到 arr
        while(i < lenA){
            arr[k] = A[i];
            i++;
            k++;
        }
        //左子数列已经结束，将右子数列剩余的数复制到 arr
        while(j < lenB){
            arr[k] = B[j];
            j++;
            k++;
        }
    }

    public static void mergesort(int[] arr, int head, int tail){
        if(head < tail){
            int mid = (head + tail) / 2;
            mergesort(arr, head, mid);
            mergesort(arr, mid+1, tail);
            merge(arr, head, mid, tail);    //合并
        }
    }
}