十大經典排序算法 Java 實現全解析：原理、複雜度、優化與選型指南

排序算法全景圖

Java 完整實現代碼庫

1. 冒泡排序

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

2. 選擇排序

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

3. 插入排序

public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

4. 希爾排序

public static void shellSort(int[] arr) {
    int n = arr.length;
    // 增量序列: n/2, n/4, ..., 1 (可優化為 Sedgewick 序列)
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int key = arr[i];
            int j = i;
            while (j >= gap && arr[j - gap] > key) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = key;
        }
    }
}

5. 歸並排序

public static void mergeSort(int[] arr) {
    if (arr.length < 2) return;
    int[] temp = new int[arr.length];
    mergeSort(arr, 0, arr.length - 1, temp);
}

private static void mergeSort(int[] arr, int left, int right, int[] temp) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid, temp);
    mergeSort(arr, mid + 1, right, temp);
    merge(arr, left, mid, right, temp);
}

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

6. 快速排序 (雙路/三路優化)

public static void quickSort(int[] arr) {
    quickSort(arr, 0, arr.length - 1);
}

private static void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;
    
    // 三數取中選樞軸
    int mid = left + (right - left) / 2;
    if (arr[left] > arr[mid]) swap(arr, left, mid);
    if (arr[left] > arr[right]) swap(arr, left, right);
    if (arr[mid] > arr[right]) swap(arr, mid, right);
    swap(arr, mid, right - 1);  // 樞軸藏到 right-1
    
    int pivot = arr[right - 1];
    int i = left, j = right - 1;
    while (true) {
        while (arr[++i] < pivot);
        while (arr[--j] > pivot);
        if (i >= j) break;
        swap(arr, i, j);
    }
    swap(arr, i, right - 1);  // 歸位樞軸
    
    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
}

// 大量重複元素用三路快排 (Dutch National Flag)
public static void quickSort3Way(int[] arr) {
    quickSort3Way(arr, 0, arr.length - 1);
}

private static void quickSort3Way(int[] arr, int left, int right) {
    if (left >= right) return;
    int lt = left, gt = right;
    int pivot = arr[left];
    int i = left + 1;
    while (i <= gt) {
        if (arr[i] < pivot) swap(arr, lt++, i++);
        else if (arr[i] > pivot) swap(arr, i, gt--);
        else i++;
    }
    quickSort3Way(arr, left, lt - 1);
    quickSort3Way(arr, gt + 1, right);
}

7. 堆排序

public static void heapSort(int[] arr) {
    int n = arr.length;
    // 1. 建最大堆 (從最後一個非葉子節點開始下沉)
    for (int i = n / 2 - 1; i >= 0; i--) {
        sink(arr, i, n);
    }
    // 2. 反復交換堆頂到末尾，縮小堆範圍
    while (n > 1) {
        swap(arr, 0, --n);
        sink(arr, 0, n);
    }
}

private static void sink(int[] arr, int k, int n) {
    while (2 * k + 1 < n) {
        int j = 2 * k + 1;  // 左子節點
        if (j + 1 < n && arr[j] < arr[j + 1]) j++;  // 取較大子節點
        if (arr[k] >= arr[j]) break;
        swap(arr, k, j);
        k = j;
    }
}

8. 計數排序

public static void countingSort(int[] arr) {
    if (arr.length == 0) return;
    int max = Arrays.stream(arr).max().getAsInt();
    int min = Arrays.stream(arr).min().getAsInt();
    int range = max - min + 1;
    
    int[] count = new int[range];
    for (int num : arr) count[num - min]++;
    
    // 累加計數 (穩定性關鍵)
    for (int i = 1; i < range; i++) count[i] += count[i - 1];
    
    int[] output = new int[arr.length];
    // 逆序遍歷保證穩定
    for (int i = arr.length - 1; i >= 0; i--) {
        output[--count[arr[i] - min]] = arr[i];
    }
    System.arraycopy(output, 0, arr, 0, arr.length);
}

9. 基數排序 (LSD)

public static void radixSort(int[] arr) {
    if (arr.length == 0) return;
    int max = Arrays.stream(arr).max().getAsInt();
    
    // 按位數從低到高 (個位、十位、百位...)
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countingSortByDigit(arr, exp);
    }
}

private static void countingSortByDigit(int[] arr, int exp) {
    int n = arr.length;
    int[] output = new int[n];
    int[] count = new int[10];  // 0-9 十進制
    
    for (int num : arr) count[(num / exp) % 10]++;
    for (int i = 1; i < 10; i++) count[i] += count[i - 1];
    for (int i = n - 1; i >= 0; i--) {
        output[--count[(arr[i] / exp) % 10]] = arr[i];
    }
    System.arraycopy(output, 0, arr, 0, n);
}

10. 桶排序

public static void bucketSort(double[] arr) {
    if (arr.length == 0) return;
    int n = arr.length;
    List[] buckets = new List[10];  // 10 個桶
    for (int i = 0; i < 10; i++) buckets[i] = new ArrayList<>();
    
    // 1. 分桶 (假設數據在 [0,1) 區間均勻分佈)
    for (double num : arr) {
        int idx = (int) (num * 10);
        buckets[idx].add(num);
    }
    
    // 2. 桶內排序 (插入排序或 Collections.sort)
    for (List bucket : buckets) {
        Collections.sort(bucket);
    }
    
    // 3. 合併
    int idx = 0;
    for (List bucket : buckets) {
        for (double num : bucket) arr[idx++] = num;
    }
}

Java 語言特有優化技巧

1. 基本類型數組 vs 對象數組

// 基本類型 int[] - 連續內存、無對象頭、緩存友好、排序最快
// 對象類型 Integer[] - 間接引用、GC 壓力大、比較需拆箱
Arrays.sort(intArr);        // 雙軸快排
Arrays.sort(IntegerArr);    // TimSort (歸並+插入混合)，穩定

2. Arrays.sort() 內部實現

• 基本類型：雙軸快速排序, O(n log n), 不穩定
• 對象類型：TimSort (Python/Java 默認), O(n log n), 穩定
• 並行排序：Arrays.parallelSort() (Java 8+), 多核加速

3. Comparator 複用

// 多字段排序
Arrays.sort(users, Comparator
    .comparing(User::getAge)
    .thenComparing(User::getName)
    .thenComparing(User::getSalary, Comparator.reverseOrder()));

選型決策樹

需要穩定排序？
├─ 是 → 數據量小/近乎有序 → 插入排序
│       數據量大、內存充足 → 歸並排序 / TimSort (Arrays.sort 對象數組)
│       整數、範圍小 → 計數排序 / 基數排序
│       浮點數、均勻分佈 → 桶排序
└─ 否 → 通用高性能 → 快速排序 (Arrays.sort 基本類型)
        實時系統/內存極限 → 堆排序
        極小數據/教學 → 選擇/冒泡/插入

性能實測參考 (10萬隨機整數)

算法              耗時(ms)  備註
Arrays.parallelSort()   12    並行雙軸快排，多核最快
Arrays.sort(int[])      18    雙軸快排
快速排序(三路)          22    手寫優化
歸並排序                35    穩定，需輔助數組
堆排序                  48    原地，無遞歸
希爾排序                65    間隔序列影響大
插入排序               1200   僅適合小數據
選擇排序               1800   寫入少但比較多
冒泡排序               4500   最慢

總結

掌握十大排序算法的 時間/空間複雜度、穩定性、適用邊界 是工程師基本功。實際開發中：

1. 首選 Arrays.sort() / Collections.sort()：經過極致優化、處理邊界情況、並行支持
2. 理解底層原理：面試必考、調優時知其然更知其所以然
3. 特殊場景手寫：Top K 用堆、外部排序用歸並、整數範圍小用計數/基數、近乎有序用插入
4. 穩定性決定架構：多關鍵字排序、去重保留首現等場景必須穩定排序

建議將上述代碼整理為個人算法工具類，配合單元測試驗證正確性，隨時可用。