合併排序

排序法採用經典的「分治策略」將問題分成一些小的問題然後遞迴求解，而「治」的階段則將分的階段得到的各答案修補在一起，即分而治之。

概念解析

我看完完整的教學之後，對於合併排序的概念首要的就是「分」，透過把數據變成兩個相同大小的子陣列，一直分化下去直到每組都只有一個元素。接下來就是將最一開始分開的兩個子序列合併在一起，將i索引指向原先在左側子序列的第一元素，將j索引指向原先在又側子序列的第一元素(mid+1)，此時將i&j做比較，較小值移到左側，重複比較直至結束。

程式範例試做:

import java.util.Arrays;

public class Alex1012_1 {
    public static void main(String[] args) {
        int arr[] = {182, 190, 242, 79, 23, 42, 749, 92};
        System.out.println("原序列為："+Arrays.toString(arr));
        int temp[] = new int[arr.length];
        Alex1012_1(arr, 0, arr.length - 1, temp);
        System.out.println("合併排序後序列為："+Arrays.toString(arr));
    }

    // "分而治之"
    public static void Alex1012_1(int[] arr, int left, int right, int[] temp) {
        if(left < right) {
            int mid = (left + right) / 2;
            // 向左遞迴進行分解
            Alex1012_1(arr, left, mid, temp);
            // 向右遞迴進行分解
            Alex1012_1(arr, mid + 1, right, temp);
            // 合併
            merge(arr, left, mid, right, temp);
        }
    }

    // merge
    public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left; // 初始化i, 左邊有序序列的初始索引
        int j = mid + 1; // 初始化j, 右邊有序序列的初始索引
        int t = 0; // 指向temp陣列的當前索引

        // step1)左右子序列比大小, 將小的放到temp陣列
        while(i <= mid && j <= right) { // 左右子序列都還沒遍歷到最後時
            if(arr[i] <= arr[j]) { 
            // 若左子序列值小於等於右子序列值，則將之放到 temp 陣列中
                temp[t] = arr[i];
                t += 1; // temp陣列索引後移
                i += 1; // 遍歷下一個
            } else { // 右子序列值小於等於左子序列值
                temp[t] = arr[j];
                t += 1;
                j += 1;
            }
        }

        // step2) 把有剩餘數據的子序列依次全部放入temp
        while(i <= mid) { // 左子序列有剩餘的元素
            temp[t] = arr[i];
            t += 1;
            i += 1;
        }

        while(j <= right) { // 右子序列有剩餘的元素
            temp[t] = arr[j];
            t += 1;
            j += 1;
        }

        // step3) 將 tmep 陣列的元素 copy 到 arr , 並不是每次都 copy 所有數據
        t = 0;
        int tempLeft = left; // 用於暫時遍歷 temp 陣列
        while(tempLeft <= right) {
            arr[tempLeft++] = temp[t++];
    }
}

程式執行結果:

原序列為：[182, 190, 242, 79, 23, 42, 749, 92]
合併排序後序列為：[23, 42, 79, 92, 182, 190, 242, 749]

時間複雜度

最佳：O(nlogⁿ) log是在次方項喔!
平均：O(nlogⁿ) log是在次方項喔!
最差：O(nlogⁿ) log是在次方項喔!