Java 經典排序算法大全：原理、實現、效能測試與選型指南

前言：為什麼還要手寫排序？

雖然生產環境直接用 Arrays.sort()/Collections.sort()（TimSort，O(n log n) 穩定），但理解經典算法是面試必考、演算法思維訓練、特定場景（如外部排序、Top-K、近似有序資料）優化的基石。本文整理 14 種常見排序，附完整 Java 實現、原理圖解、效能實測（20,000 筆隨機整數）與選型建議。

一、O(n²) 基礎排序（教學/小規模/近似有序）

1. 冒泡排序

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

• 特點：穩定、原地、最差/平均 O(n²)，最佳 O(n)（已有序）。

2. 改良冒泡（旗標提前結束）

public static void bubbleSortAdv(int[] a) {
    boolean swapped = true;
    for (int limit = a.length - 1; swapped && limit > 0; limit--) {
        swapped = false;
        for (int i = 0; i < limit; i++)
            if (a[i] > a[i+1]) { swap(a, i, i+1); swapped = true; }
    }
}

3. 改良冒泡 II（記錄最後交換位置）

public static void bubbleSortAdv2(int[] a) {
    int limit = a.length - 1;
    while (limit > 0) {
        int lastSwap = 0;
        for (int i = 0; i < limit; i++)
            if (a[i] > a[i+1]) { swap(a, i, i+1); lastSwap = i+1; }
        limit = lastSwap;
    }
}

4. 選擇排序

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

• 特點：不穩定、原地、交換次數最少 (n-1)，適合寫入成本高的存儲介質。

5. 插入排序

public static void insertSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int tmp = a[i], j = i-1;
        while (j >= 0 && a[j] > tmp) a[j+1] = a[j--];
        a[j+1] = tmp;
    }
}

• 特點：穩定、原地、近似有序資料 O(n)、線上算法（可邊讀邊排）。

6. 改良插入（二分查找插入位置）

public static void insertSortBin(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int tmp = a[i], pos = Arrays.binarySearch(a, 0, i, tmp);
        if (pos < 0) pos = -pos - 1;
        System.arraycopy(a, pos, a, pos+1, i-pos);
        a[pos] = tmp;
    }
}

二、O(n log n) 高效排序（生產級主力）

7. 希爾排序（插入排序改良，縮小增量）

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 tmp = a[i], j = i;
            while (j >= gap && a[j-gap] > tmp) { a[j] = a[j-gap]; j -= gap; }
            a[j] = tmp;
        }
}

• 特點：不穩定、原地、增量序列影響巨大（Hibbard、Sedgewick、Ciura 序列可達 O(n^1.25)）。

8. 歸併排序

public static int[] mergeSort(int[] a) {
    if (a.length <= 1) return a;
    int mid = a.length/2;
    int[] left = mergeSort(Arrays.copyOfRange(a, 0, mid));
    int[] right = mergeSort(Arrays.copyOfRange(a, mid, a.length));
    return merge(left, right);
}
private static int[] merge(int[] a, int[] b) {
    int[] r = new int[a.length + b.length];
    int i=0,j=0,k=0;
    while (i

public static void quickSort(int[] a, int lo, int hi) {
    if (lo >= hi) return;
    int i = lo, j = hi, pivot = a[lo];
    while (i < j) {
        while (i < j && a[j] >= pivot) j--;
        if (i < j) a[i++] = a[j];
        while (i < j && a[i] <= pivot) i++;
        if (i < j) a[j--] = a[i];
    }
    a[i] = pivot;
    quickSort(a, lo, i-1);
    quickSort(a, i+1, hi);
}
public static void quickSort(int[] a) { quickSort(a, 0, a.length-1); }

public static void heapSort(int[] a) {
    for (int i = (a.length-2)/2; i >= 0; i--) maxHeapify(a, i, a.length);
    for (int i = a.length-1; i > 0; i--) {
        swap(a, 0, i);
        maxHeapify(a, 0, i);
    }
}
private static void maxHeapify(int[] a, int i, int len) {
    int tmp = a[i];
    for (int j = 2*i+1; j < len; j = 2*j+1) {
        if (j+1 < len && a[j+1] > a[j]) j++;
        if (a[j] < tmp) break;
        a[i] = a[j]; i = j;
    }
    a[i] = tmp;
}