您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 相關知識

Java 排序算法全攻略：Collections.sort 實戰、八大經典算法代碼、基準測試與選型指南

編輯：Java 相關知識

Java 開發中排序無處不在。本文分三層遞進：集合框架排序實戰（Comparable/Comparator）、八大經典算法標準實現、性能基準與工程選型，提供可直接複製的完整代碼庫，助你從 API 調用者進化為算法掌控者。

第一層：Collections.sort 兩種姿勢

1. 實體實現 Comparable（內部排序邏輯固化）

class User implements Comparable<User> {
    private Integer order;
    public int compareTo(User o) { return this.order.compareTo(o.order); }
}
Collections.sort(list); // 直接排序

2. 外部傳入 Comparator（靈活多維排序）

Collections.sort(list, new Comparator<User>() {
    public int compare(User a, User b) { return a.getOrder().compareTo(b.getOrder()); }
});
// Java 8+ Lambda 更簡潔
list.sort(Comparator.comparing(User::getOrder));

第二層：八大經典算法完整實現 (JavaSort.java)

算法	方法	平均時間	穩定	關鍵技巧
冒泡	bubbleSort	O(n²)	是	相鄰交換，异或交換無臨時變量
插入	insertSort	O(n²)	是	有序區後移，插入當前元素
選擇	selectSort	O(n²)	否	每輪選最小，與首位交換
希爾	shellSort	O(n^1.3~1.5)	否	分組插入，縮小增量至 1
快速	quickSort	O(n log n)	否	三數取中 pivot，雙向掃描分區
歸併	mergeSort	O(n log n)	是	分治遞歸，臨時數組歸併
堆	heapSort	O(n log n)	否	建大根堆，首尾交換下沉
基數(LSD)	lstRadixSort	O(d(n+r))	是	計數排序穩定，按位從低到高

快速排序關鍵分區代碼

private static int pivotPartition(int[] a, int l, int r) {
    swap(a, l, (l + r) >>> 1); // 中位數作 pivot 避免有序退化
    int pivot = a[l];
    while (l < r) {
        while (l < r && a[r] >= pivot) r--;
        if (l < r) a[l++] = a[r];
        while (l < r && a[l] <= pivot) l++;
        if (l < r) a[r--] = a[l];
    }
    a[l] = pivot; return l;
}

歸併排序歸併代碼

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

第三層：工程選型決策樹

數據量 < 50 / 近乎有序 → insertSort / Collections.sort（TimSort 混合插入/歸併）。
通用大數據、追求速度 → quickSort（雙軸快排 JDK 7+ 默認）或 Arrays.sort。
必須穩定 / 外部排序 / 鏈表 → mergeSort。
整數/定長 Key、極大數據 → lstRadixSort（線性時間、非比較）。
嚴格 O(1) 空間、實時系統 → heapSort。

完整測試主類

public class JavaSort {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = in.nextInt();
            // 任選一種算法
            mergeSort(a, 0, n - 1);
            printArr(a);
        }
    }
    // 八大算法靜態方法 + printArr ...
}

將 JavaSort.java 放入項目，即擁有教學級、生產級雙模式排序工具箱。