Java 非遞歸快速排序：基於二叉樹模擬棧實現百萬級資料高效排序

為何捨棄遞歸？

傳統遞歸快速排序在資料量極大（如 800 萬）時極易導致 StackOverflowError。雖然可透過 -Xss 增加棧大小，但治標不治本。本文採用顯式二叉樹模擬遞歸棧，將遞歸轉為迭代，徹底解決棧溢出問題，且保持 O(N log N) 平均時間複雜度。

演算法核心思想

1. 每個節點代表一個待排序的陣列區間 [left, right]。
2. 根節點代表整個陣列 [0, n-1]。
3. 分區：以 left 索引元素為基準，雙指針交換，使基準左邊全大於基準，右邊全小於基準（降序），基準最終位置為 mid。
4. 左子區間 [left, mid-1] 為左子節點，右子區間 [mid+1, right] 為右子節點。
5. 先序遍歷（根→左→右）處理每個節點，遍歷完成即排序結束。

二叉樹節點定義

class Binary {
    private int left, right;           // 區間邊界
    private Binary beforeBinary;       // 父節點
    private Binary leftBinary;         // 左子節點（左區間）
    private Binary rightBinary;        // 右子節點（右區間）
    // getter/setter 省略
}

排序主流程

public static void quick_sort(int[] arr) {
    Binary root = new Binary(0, arr.length - 1);
    root.setBefore(null);
    Binary curr = root;

    do {
        // 1. 分區
        int l = curr.getLeft();
        int r = curr.getRight();
        int pivot = arr[l];
        while (l < r) {
            while (l < r && pivot >= arr[r]) r--;
            if (l < r) arr[l++] = arr[r];
            while (l < r && pivot <= arr[l]) l++;
            if (l < r) arr[r--] = arr[l];
        }
        arr[l] = pivot; // l == r == mid

        // 2. 建立子節點
        if (r < curr.getRight() - 1) {
            Binary rightChild = new Binary(r + 1, curr.getRight());
            curr.setRightBinary(rightChild);
            rightChild.setBefore(curr);
        }
        if (l - 1 > curr.getLeft()) {
            Binary leftChild = new Binary(curr.getLeft(), l - 1);
            curr.setLeftBinary(leftChild);
            leftChild.setBefore(curr);
        }

        // 3. 遍歷策略：優先左子樹，左無則右，右也無則回父節點
        boolean moved = false;
        do {
            if (curr.getLeftBinary() != null) {
                Binary next = curr.getLeftBinary();
                curr.setLeftBinary(null); // 關鍵：斷開引用，允許 GC
                curr = next;
                moved = true;
            } else if (curr.getRightBinary() != null) {
                Binary next = curr.getRightBinary();
                curr.setRightBinary(null);
                curr = next;
                moved = true;
            } else {
                if (curr == root) break; // 回到根節點，結束
                curr = curr.getBeforeBinary(); // 回父節點
            }
        } while (!moved);
    } while (curr != root);
}

效能實測（JDK 8、Intel i7、8GB Heap）

優缺點總結

圖解分區過程

進階優化方向

• 基準選取：隨機索引或「三數取中」。
• 小區間切換插入排序（閾值 16~32）。
• 尾遞歸消除：迭代處理較大區間，遞歸處理較小區間。
• 並行化：使用 ForkJoinPool 併行處理左右子樹。