圖解 Java 8 大經典排序演算法：原理、實作與效能比較

排序演算法是程式設計的基石，也是面試必考題。本文系統整理 8 大經典排序演算法：插入排序、希爾排序、選擇排序、堆排序、冒泡排序、快速排序、合併排序、基數排序，涵蓋分類原理、動圖示意、Java 完整實作與時空複雜度比較表，助你建立完整排序知識體系。

一、分類總覽

關鍵結論： 平均速度最快為快速排序；額外空間最少為堆排序（O(1)）；最多為合併排序（O(n)）。

二、各演算法核心原理與 Java 實作

1. 直接插入排序

思想： 將陣列分為「已排序區」與「未排序區」，每次從未排序區取出首個元素，插入已排序區適當位置。

public static void insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int temp = a[i];
        int j = i - 1;
        while (j >= 0 && temp < a[j]) {
            a[j + 1] = a[j]; // 後移
            j--;
        }
        a[j + 1] = temp;
    }
}

2. 希爾排序（縮小增量排序）

思想： 先按增量 gap = n/2 分組進行插入排序，逐步縮小增量至 1。

public static void shellSort(int[] a) {
    for (int gap = a.length / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < a.length; i++) {
            int temp = a[i];
            int j = i - gap;
            while (j >= 0 && temp < a[j]) {
                a[j + gap] = a[j];
                j -= gap;
            }
            a[j + gap] = temp;
        }
    }
}

3. 簡單選擇排序

思想： 每輪從未排序區選出最小值，與未排序區首位交換。

public static void selectionSort(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < a.length; j++) {
            if (a[j] < a[minIdx]) minIdx = j;
        }
        swap(a, i, minIdx);
    }
}

4. 堆排序

思想： 將陣列視為完全二元樹，建立大頂堆，反覆將堆頂（最大值）與末尾交換，並對剩餘元素重建堆。

public static void heapSort(int[] a) {
    int n = a.length;
    // 建堆
    for (int i = (n - 2) / 2; i >= 0; i--) siftDown(a, i, n - 1);
    // 排序
    for (int end = n - 1; end > 0; end--) {
        swap(a, 0, end);
        siftDown(a, 0, end - 1);
    }
}

private static void siftDown(int[] a, int root, int end) {
    while (true) {
        int child = 2 * root + 1;
        if (child > end) break;
        if (child + 1 <= end && a[child] < a[child + 1]) child++;
        if (a[root] >= a[child]) break;
        swap(a, root, child);
        root = child;
    }
}
private static void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }

5. 冒泡排序

思想： 相鄰元素兩兩比較，大的往後沉，小的往前冒；每輪將最大值推到末尾。

public static void bubbleSort(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        boolean swapped = false;
        for (int j = 0; j < a.length - 1 - i; j++) {
            if (a[j] > a[j + 1]) { swap(a, j, j + 1); swapped = true; }
        }
        if (!swapped) break; // 已有序提前結束
    }
}

6. 快速排序

思想： 分治法。選基準值，將陣列分為「小於基準」與「大於等於基準」兩部分，遞歸排序兩部分。

public static void quickSort(int[] a, int low, int high) {
    if (low < high) {
        int pivot = partition(a, low, high);
        quickSort(a, low, pivot - 1);
        quickSort(a, pivot + 1, high);
    }
}

private static int partition(int[] a, int low, int high) {
    int pivotVal = a[low];
    while (low < high) {
        while (low < high && a[high] >= pivotVal) high--;
        a[low] = a[high];
        while (low < high && a[low] <= pivotVal) low++;
        a[high] = a[low];
    }
    a[low] = pivotVal;
    return low;
}

7. 合併排序

思想： 分治法。遞歸將陣列拆分至單元素，再合併兩個有序子陣列為有序陣列。

public static void mergeSort(int[] a, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(a, left, mid);
        mergeSort(a, mid + 1, right);
        merge(a, left, mid, right);
    }
}

private static void merge(int[] a, int left, int mid, int right) {
    int[] tmp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= right) tmp[k++] = a[j++];
    System.arraycopy(tmp, 0, a, left, tmp.length);
}

8. 基數排序（LSD）

思想： 從最低位到最高位，依位數分配至 0~9 桶，再收集；重複至最高位完成排序。

public static void radixSort(int[] a) {
    int max = Arrays.stream(a).max().orElse(0);
    for (int exp = 1; max / exp > 0; exp *= 10) {
        List<Integer>[] buckets = new ArrayList[10];
        for (int b = 0; b < 10; b++) buckets[b] = new ArrayList<>();
        for (int v : a) buckets[(v / exp) % 10].add(v);
        int idx = 0;
        for (List<Integer> bucket : buckets) for (int v : bucket) a[idx++] = v;
    }
}

三、效能實測建議

• 小資料量（< 50）： 插入排序常因常數因子小而最快。
• 通用大資料量： 快速排序（雙軸快排如 Arrays.sort()）最優。
• 需穩定排序： 合併排序或 TimSort（Java 內建 Arrays.sort(Object[])）。
• 整數且範圍已知： 基數排序可達 O(n) 線性時間。

掌握這 8 大排序的原理邊界與適用場景，是演算法功力的重要標誌。