十大經典 Java 排序算法完整實現與複雜度分析

算法總覽

1. 選擇排序

原理：每輪從無序區選出最小元素，與無序區首位交換。

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

2. 插入排序

原理：將無序區元素逐個插入有序區適當位置，類似整理撲克牌。

public static void insertSort(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;
    }
}

3. 冒泡排序

原理：相鄰元素兩兩比較，大的「冒泡」到右側。

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

4. 歸併排序

原理：分治法，遞歸拆分至單元素，再合併有序子陣列。

public static void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

private static void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;
    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, 0, arr, left, temp.length);
}

5. 快速排序

原理：選基準值，小者左大者右，遞歸處理左右子陣列。

public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);
        quickSort(arr, low, pivot - 1);
        quickSort(arr, pivot + 1, high);
    }
}

private static int partition(int[] arr, int low, int high) {
    int pivot = arr[low];
    while (low < high) {
        while (low < high && arr[high] >= pivot) high--;
        arr[low] = arr[high];
        while (low < high && arr[low] <= pivot) low++;
        arr[high] = arr[low];
    }
    arr[low] = pivot;
    return low;
}

6. 希爾排序

原理：分組插入排序，間隔逐漸縮小至 1。

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

7. 堆排序（小頂堆）

原理：建堆 → 堆頂與末尾交換 → 縮小堆範圍 → 重新調整。

public static void heapSort(int[] arr) {
    // 建堆
    for (int i = arr.length / 2 - 1; i >= 0; i--) {
        adjustHeap(arr, i, arr.length - 1);
    }
    // 排序
    for (int i = arr.length - 1; i > 0; i--) {
        swap(arr, 0, i);
        adjustHeap(arr, 0, i - 1);
    }
}

private static void adjustHeap(int[] arr, int parent, int end) {
    int child = 2 * parent + 1;
    while (child <= end) {
        if (child + 1 <= end && arr[child + 1] < arr[child]) child++;
        if (arr[child] < arr[parent]) {
            swap(arr, parent, child);
            parent = child;
            child = 2 * parent + 1;
        } else break;
    }
}

private static void swap(int[] arr, int i, int j) {
    int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
}

實戰選擇指南

• 小數據量 (n < 50)：插入排序、希爾排序
• 通用高效排序：快速排序（Java Arrays.sort() 雙軸快排）、歸併排序
• 需穩定排序：歸併排序、TimSort（Java 對象排序默認）
• 空間受限：堆排序、快速排序
• 近乎有序數據：插入排序、TimSort 極快

Java 內置排序最佳實踐

// 基本類型：雙軸快排（不穩定，極快）
Arrays.sort(intArray);

// 對象類型：TimSort（穩定，適應性強）
Arrays.sort(objArray);
Arrays.sort(objArray, Comparator.comparing(User::getAge));

// List 排序
list.sort(Comparator.comparing(User::getName));
Collections.sort(list, (a, b) -> a.getAge() - b.getAge());

實際開發中 優先使用 JDK 內置排序，僅在極特殊場景（如嵌入式、教學、特定算法題）才手寫排序。