Java 經典 6 大排序算法深度解析與實現

算法複雜度總覽

核心代碼實現

1. 選擇排序

public static <T extends Comparable<T>> void selectionSort(T[] a, boolean asc) {
    for (int i = 0; i < a.length; i++) {
        int sel = i;
        for (int j = i + 1; j < a.length; j++)
            if (compare(a[j], a[sel], asc) < 0) sel = j;
        swap(a, i, sel);
    }
}

2. 插入排序

public static <T extends Comparable<T>> void insertionSort(T[] a, boolean asc) {
    for (int i = 1; i < a.length; i++) {
        T tmp = a[i];
        int j = i;
        for (; j > 0 && compare(a[j-1], tmp, asc) > 0; j--)
            a[j] = a[j-1];
        a[j] = tmp;
    }
}

3. 冒泡排序（優化版）

public static <T extends Comparable<T>> void bubbleSort(T[] a, boolean asc) {
    int n = a.length, last = 0;
    for (int i = 0; i < n; i++) {
        boolean swapped = false;
        int curr = Math.max(last, i);
        for (int j = n - 1; j > curr; j--) {
            if (compare(a[j-1], a[j], asc) > 0) {
                swap(a, j-1, j);
                swapped = true; last = j;
            }
        }
        if (!swapped) break;
    }
}

4. 希爾排序

public static <T extends Comparable<T>> void shellSort(T[] a, boolean asc) {
    int n = a.length, gap = 1;
    while (gap < n / 3) gap = gap * 3 + 1; // Knuth 序列
    while (gap >= 1) {
        for (int i = gap; i < n; i++) {
            T tmp = a[i];
            int j = i;
            for (; j >= gap && compare(a[j-gap], tmp, asc) > 0; j -= gap)
                a[j] = a[j-gap];
            a[j] = tmp;
        }
        gap /= 3;
    }
}

5. 歸併排序（優化：小數組用插入、有序跳過合併）

public static <T extends Comparable<T>> void mergeSort(T[] a, boolean asc) {
    @SuppressWarnings("unchecked") T[] aux = (T[]) new Comparable[a.length];
    mergeSort(a, aux, 0, a.length - 1, asc);
}

private static <T extends Comparable<T>> void mergeSort(T[] a, T[] aux, int lo, int hi, boolean asc) {
    if (hi - lo < 20) { insertionSort(a, lo, hi, asc); return; } // 小數組切換插入
    int mid = lo + (hi - lo) / 2;
    mergeSort(a, aux, lo, mid, asc);
    mergeSort(a, aux, mid + 1, hi, asc);
    if (compare(a[mid], a[mid+1], asc) <= 0) return; // 已有序跳過合併
    merge(a, aux, lo, mid, hi, asc);
}

private static <T extends Comparable<T>> void merge(T[] a, T[] aux, int lo, int mid, int hi, boolean asc) {
    System.arraycopy(a, lo, aux, lo, hi - lo + 1);
    int i = lo, j = mid + 1;
    for (int k = lo; k <= hi; k++) {
        if (i > mid) a[k] = aux[j++];
        else if (j > hi) a[k] = aux[i++];
        else if (compare(aux[i], aux[j], asc) <= 0) a[k] = aux[i++];
        else a[k] = aux[j++];
    }
}

6. 快速排序（三向切分優化重複鍵）

public static <T extends Comparable<T>> void quickSort(T[] a, boolean asc) {
    quickSort(a, 0, a.length - 1, asc);
}

private static <T extends Comparable<T>> void quickSort(T[] a, int lo, int hi, boolean asc) {
    if (hi - lo < 20) { insertionSort(a, lo, hi, asc); return; }
    int lt = lo, gt = hi, i = lo + 1;
    T pivot = a[lo];
    while (i <= gt) {
        int cmp = compare(a[i], pivot, asc);
        if (cmp < 0) swap(a, lt++, i++);
        else if (cmp > 0) swap(a, i, gt--);
        else i++;
    }
    quickSort(a, lo, lt - 1, asc);
    quickSort(a, gt + 1, hi, asc);
}

輔助方法

private static <T extends Comparable<T>> int compare(T a, T b, boolean asc) {
    int c = a.compareTo(b);
    return asc ? c : -c;
}
private static void swap(Object[] a, int i, int j) { Object t = a[i]; a[i] = a[j]; a[j] = t; }

選型指南

• 小數組/近乎有序：插入排序（或作為遞歸基準）。
• 通用高性能：快速排序（JDK Arrays.sort 基礎）。
• 穩定排序/外部排序：歸併排序。
• 空間受限/中等規模：希爾排序。
• 教學/極小數據：選擇/冒泡。

總結

理解各算法時空權衡、穩定性、適用場景，面試手寫核心邏輯（分區、合併、插入），工程中優先用 Arrays.sort/Collections.sort（雙軸快排 + 歸併），必要時自定義 Comparator 或實現特定優化。