Java 數組排序四大經典算法實現與性能對比：快排、冒泡、選擇、插入

掌握基礎排序算法是程序員內功心法。本文提供 Java 實現的四種經典排序：快速排序（Arrays.sort）、冒泡排序、選擇排序、插入排序，附完整代碼、複雜度分析與工程選型建議。

1. 快速排序 —— 工程首選 Arrays.sort()

import java.util.Arrays;

public class QuickSortDemo {
    public static void main(String[] args) {
        int[] arr = {5, 4, 2, 4, 9, 1};
        Arrays.sort(arr); // 雙軸快排 (Java 7+) / TimSort (對象數組)
        System.out.println(Arrays.toString(arr)); // [1, 2, 4, 4, 5, 9]
    }
}

特點：JDK 內部高度優化（基本類型雙軸快排，對象類型 TimSort），平均 O(n log n)，穩定（對象版），生產環境直接用，勿造輪子。

2. 冒泡排序 —— 教學入門，實戰慎用

public static int[] bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[i] > arr[j]) {
                int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
            }
        }
    }
    return arr;
}

複雜度：比較 O(n²)，交換 O(n²)。
優化：加入 boolean swapped 標記，單輪無交換則提前結束（最好情況 O(n)）。

3. 選擇排序 —— 減少交換次數

public static int[] selectSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[minIdx] > arr[j]) minIdx = j;
        }
        if (minIdx != i) {
            int tmp = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = tmp;
        }
    }
    return arr;
}

複雜度：比較 O(n²)，交換 O(n)（每輪最多一次交換）。
場景：交換操作極其昂貴（如大對象移動）時優於冒泡。

4. 插入排序 —— 小數據/近乎有序數據的王者

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

複雜度：比較 O(n²)，移動/複製 O(n²)（最好情況已有序 O(n)）。
優勢：穩定排序、原地排序、適應性強（數據基本有序時極快），JDK Arrays.sort 小數組閾值（<47）會切換到插入排序。

性能對比總結表

實戰選型指南

1. 一般業務排序：Arrays.sort() / Collections.sort() / List.sort() —— 無腦用，JDK 已幫你做好所有優化。
2. 海量數據外部排序：歸並排序 + 磁盤分片（超出內存）。
3. 特定約束場景：
   • 要求穩定 + 小數組 → 插入排序
   • 交換成本極高 → 選擇排序
   • 嵌入式/教學演示 → 冒泡/選擇/插入手寫
4. 並行排序：Java 8+ Arrays.parallelSort() 利用多核，大數組顯著加速。

面試必會手寫冒泡/選擇/插入/快排分區；工作中請擁抱 Arrays.sort。理解算法本質，是為了在關鍵時刻做出正確工程決策，而非重複造輪子。