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

排序算法是演算法基石。本文提供六大經典排序的 Java 完整實作、複雜度分析、穩定性說明與工程優化技巧。

算法分類與複雜度總覽

核心實作代碼

1. 插入排序

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

2. 希爾排序

static <E extends Comparable<? super E>> void shellSort(List<E> a) {
    int h = 1;
    while (h < a.size() / 3) h = h * 3 + 1; // Knuth 序列: 1,4,13,40,121...
    for (; h >= 1; h /= 3)
        for (int i = h; i < a.size(); i++)
            for (int j = i; j >= h && a.get(j).compareTo(a.get(j - h)) < 0; j -= h)
                Collections.swap(a, j, j - h);
}

3. 冒泡排序（優化版）

public static void bubbleSort(int[] data) {
    for (int i = data.length - 1; i > 0; --i) {
        boolean isSort = false;
        for (int j = 0; j < i; ++j) {
            if (data[j + 1] < data[j]) {
                int temp = data[j];
                data[j] = data[j + 1];
                data[j + 1] = temp;
                isSort = true;
            }
        }
        if (!isSort) break; // 無交換提前結束
    }
}

4. 快速排序（工程優化版：三數取中 + 切換插入排序）

public class Quicksort {
    public static final int CUTOFF = 11; // 小區間改用插入排序
    
    public static <T extends Comparable<? super T>> void quicksort(T[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }
    
    private static <T extends Comparable<? super T>> void quickSort(T[] arr, int left, int right) {
        if (left + CUTOFF <= right) {
            T pivot = median(arr, left, right); // 三數取中
            int i = left, j = right - 1;
            for (;;) {
                while (arr[++i].compareTo(pivot) < 0);
                while (arr[--j].compareTo(pivot) > 0);
                if (i < j) swapRef(arr, i, j);
                else break;
            }
            swapRef(arr, i, right - 1);
            quickSort(arr, left, i - 1);
            quickSort(arr, i + 1, right);
        } else {
            insertionSort(arr, left, right);
        }
    }
    // median、swapRef、insertionSort 省略...
}

5. 選擇排序

public static void selectSort(int[] data) {
    for (int i = 0; i < data.length; i++) {
        int minIndex = i;
        for (int j = i + 1; j < data.length; j++)
            if (data[j] < data[minIndex]) minIndex = j;
        if (minIndex != i) {
            int temp = data[i];
            data[i] = data[minIndex];
            data[minIndex] = temp;
        }
    }
}

6. 歸並排序

public static int[] mergeSort(int[] arr) {
    if (arr.length == 1) return arr;
    int half = arr.length / 2;
    int[] arr1 = Arrays.copyOfRange(arr, 0, half);
    int[] arr2 = Arrays.copyOfRange(arr, half, arr.length);
    return mergeSortSub(mergeSort(arr1), mergeSort(arr2));
}

private static int[] mergeSortSub(int[] arr1, int[] arr2) {
    int[] result = new int[arr1.length + arr2.length];
    int i = 0, j = 0, k = 0;
    while (i < arr1.length && j < arr2.length)
        result[k++] = (arr1[i] < arr2[j]) ? arr1[i++] : arr2[j++];
    while (i < arr1.length) result[k++] = arr1[i++];
    while (j < arr2.length) result[k++] = arr2[j++];
    return result;
}

工程選型指南

• 小數據量（<50）：插入排序、選擇排序常數項小，實際更快
• 近乎有序：插入排序 O(n)，冒泡優化版 O(n)
• 通用高效：快速排序（JDK Arrays.sort() 原始類型用雙軸快排，物件用 TimSort 歸並變體）
• 穩定性要求：歸並排序、TimSort
• 記憶體受限：堆排序 O(1) 空間（本文未含）
• 外部排序/大文件：歸並排序（順序讀寫友好）

完整測試主程式

文末提供 CommonSort 類整合所有算法（除快速排序獨立類），含 main 方法驗證輸出，可直接複製執行。