Java 實作合併排序與樹形排序（錦標賽排序）完整教學

字串分隔補充

String[] b = str.split("query|,"); // 以 "query" 或逗號分隔

合併排序（遞迴實作）

public class MergeSort2 {
    // 對 data[a, b) 區間進行合併排序
    static void mergeSort(int[] data, int a, int b) {
        if (a >= b) return;
        int mid = (a + b) / 2;
        mergeSort(data, a, mid);
        mergeSort(data, mid + 1, b);
        merge(data, a, mid, b);
    }

    // 合併兩個有序區間 [low, mid) 與 [mid, high)
    static void merge(int[] data, int low, int mid, int high) {
        int[] tmp = new int[high - low + 1];
        int[] left = new int[mid - low + 1];
        int[] right = new int[high - mid];
        for (int i = 0; i < left.length; i++) left[i] = data[low + i];
        for (int i = 0; i < right.length; i++) right[i] = data[mid + i];

        int li = 0, ri = 0, ti = 0;
        while (li < left.length && ri < right.length) {
            tmp[ti++] = (left[li] <= right[ri]) ? left[li++] : right[ri++];
        }
        while (li < left.length) tmp[ti++] = left[li++];
        while (ri < right.length) tmp[ti++] = right[ri++];

        for (int i = 0; i < ti; i++) data[low + i] = tmp[i];
    }

    public static void main(String[] args) {
        int[] a = {26, 29, 60, 60, 11, 15, 20, 75, 100, 500, 1000, 3, 5, 6, 8, 9};
        mergeSort(a, 0, a.length - 1);
        for (int v : a) System.out.print(v + " ");
    }
}

樹形排序（錦標賽排序）

利用完全二叉樹結構，葉節點存放資料，內部節點存放子樹最小值，反覆取出根節點並將對應葉節點設為 Integer.MAX_VALUE 以獲得有序序列。

public class TreeSort {
    // 建立/更新錦標賽樹
    public static int[] treeAgain(int[] a) {
        int[] tree = new int[2 * a.length - 1];
        for (int i = tree.length - 1; i >= 0; i--) {
            if (i - a.length + 1 >= 0) {
                tree[i] = a[i - a.length + 1];
            } else {
                tree[i] = Math.min(tree[i * 2 + 1], tree[i * 2 + 2]);
            }
        }
        return tree;
    }

    public static void treeSort(int[] a) {
        int[] tree;
        while (true) {
            tree = treeAgain(a);
            if (tree[0] == Integer.MAX_VALUE) break;
            System.out.print(tree[0] + " ");
            for (int i = 0; i < a.length; i++) {
                if (a[i] == tree[0]) { a[i] = Integer.MAX_VALUE; break; }
            }
        }
    }

    public static void main(String[] args) {
        int[] a = {26, 29, 60, 60, 11, 15, 20, 75, 100, 500, 1000, 3, 5, 6, 8, 9};
        treeSort(a);
    }
}

比較與適用場景

• 合併排序：穩定、O(n log n)、需額外 O(n) 空間，適合一般用途與連結列表。
• 樹形排序：空間佔用大（近 2n）、不穩定、適合需反覆取最小值的串流場景。