Java 經典排序算法完整實作：冒泡、快速、希爾、選擇、插入排序

Java 經典排序算法完整實作：冒泡、快速、希爾、選擇、插入排序

掌握基本排序算法是程式設計面試與效能優化的基石。本文提供五大經典排序算法的 Java 實作，並附上時間複雜度分析與 Arrays.sort() 實戰對比。

算法複雜度速查表

完整程式碼結構

public class SortAlgorithms {
    // 1. 插入排序
    public void insertSort(int[] a) { ... }

    // 2. 冒泡排序
    public void bubbleSort(int[] a) { ... }

    // 3. 快速排序 (遞歸分治)
    public void quickSort(int[] a) { 
        if (a.length > 1) quickSort(a, 0, a.length - 1); 
    }
    private void quickSort(int[] a, int low, int high) { ... }
    private int partition(int[] a, int low, int high) { ... }

    // 4. 選擇排序
    public void selectSort(int[] a) { ... }

    // 5. 希爾排序 (縮小增量)
    public void shellSort(int[] a) { ... }

    // 工具方法
    public void printArray(int[] a) { ... }
}

關鍵算法核心片段

快速排序 - 分區邏輯

private int partition(int[] a, int low, int high) {
    int pivot = a[low]; // 基準值
    while (low < high) {
        while (low < high && a[high] >= pivot) high--;
        a[low] = a[high];
        while (low < high && a[low] <= pivot) low++;
        a[high] = a[low];
    }
    a[low] = pivot;
    return low;
}

希爾排序 - 增量序列

public 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 && a[j] > temp) {
                a[j + gap] = a[j];
                j -= gap;
            }
            a[j + gap] = temp;
        }
    }
}

實戰測試主程式

public static void main(String[] args) {
    int[] data = {45,32,54,12,43,65,11,3,43,6,33,90,44,1,178};
    SortAlgorithms s = new SortAlgorithms();

    int[] arr = data.clone(); s.insertSort(arr);  System.out.println("插入: " + Arrays.toString(arr));
    arr = data.clone(); s.bubbleSort(arr);      System.out.println("冒泡: " + Arrays.toString(arr));
    arr = data.clone(); s.quickSort(arr);       System.out.println("快速: " + Arrays.toString(arr));
    arr = data.clone(); s.shellSort(arr);       System.out.println("希爾: " + Arrays.toString(arr));
    arr = data.clone(); s.selectSort(arr);      System.out.println("選擇: " + Arrays.toString(arr));

    // 生產環境直接用 JDK 優化實作
    arr = data.clone(); Arrays.sort(arr);       System.out.println("JDK:  " + Arrays.toString(arr));
}

工程實踐建議

• 小資料量 (n < 50)：插入排序常因低常數因子而最快。
• 一般用途：直接使用 Arrays.sort() (雙軸快速排序) 或 Collections.sort() (TimSort)，已高度優化且穩定。
• 平行排序：Java 8+ Arrays.parallelSort() 利用 Fork/Join 框架多核加速。
• 避免重造輪子：除非教學或極特殊約束 (嵌入式、特定分佈)，生產碼請勿自行實作排序。