七大經典排序算法 Java 實現與複雜度對比總結

從選擇排序到堆排序：基礎排序算法全景實戰指南

排序是演算法入門必修課，亦是面試高頻考點。本文整理 **選擇、插入、希爾、歸並、快速、堆、冒泡** 七大經典排序的 **核心思想、代碼實現、時空複雜度、穩定性、適用場景**，附帶可直接運行的 Java 代碼與動圖演示鏈接，助你建立完整排序知識體系。

算法總覽表

1. 選擇排序

核心思想

每輪從未排序區找最小元素，換到有序區末尾。

代碼

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

2. 插入排序

核心思想

將當前元素插入已排序區間適當位置，後移大於它的元素。

代碼

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

3. 希爾排序

核心思想

按增量 h 分組插入排序，逐步縮小 h 至 1（示例用 3x+1 序列：1,4,13,40...）。

代碼

public static void shellSort(int[] a) {
    int n = a.length, h = 1;
    while (h < n/3) h = 3*h + 1;
    while (h >= 1) {
        for (int i = h; i < n; i++)
            for (int j = i; j >= h && a[j] < a[j-h]; j -= h)
                { int t = a[j]; a[j] = a[j-h]; a[j-h] = t; }
        h /= 3;
    }
}

4. 歸並排序

核心思想

分治法：遞歸拆半排序，再合併兩個有序子數組。

代碼

public static void mergeSort(int[] a, int l, int r) {
    if (l < r) {
        int m = (l + r) >>> 1;
        mergeSort(a, l, m);
        mergeSort(a, m+1, r);
        merge(a, l, m, r);
    }
}
private static void merge(int[] a, int l, int m, int r) {
    int[] tmp = new int[r-l+1];
    int i = l, j = m+1, k = 0;
    while (i <= m && j <= r) tmp[k++] = a[i] < a[j] ? a[i++] : a[j++];
    while (i <= m) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    System.arraycopy(tmp, 0, a, l, tmp.length);
}

5. 快速排序

核心思想

選基準值，雙指針分區：左邊 ≤ 基準，右邊 ≥ 基準，遞歸處理左右子區。

代碼

public static void quickSort(int[] a, int l, int r) {
    if (l < r) {
        int p = partition(a, l, r);
        quickSort(a, l, p-1);
        quickSort(a, p+1, r);
    }
}
private static int partition(int[] a, int l, int r) {
    int key = a[l], i = l, j = r;
    while (i < j) {
        while (i < j && a[j] >= key) j--;
        if (i < j) a[i++] = a[j];
        while (i < j && a[i] <= key) i++;
        if (i < j) a[j--] = a[i];
    }
    a[i] = key; return i;
}

6. 堆排序

核心思想

構建最小堆，反覆交換堆頂與末尾元素，再下沉調整堆。

代碼（降序輸出）

public static void heapSort(int[] a) {
    int n = a.length;
    for (int i = n/2 - 1; i >= 0; i--) minHeapFixdown(a, i, n);
    for (int i = n-1; i >= 1; i--) {
        int t = a[0]; a[0] = a[i]; a[i] = t;
        minHeapFixdown(a, 0, i);
    }
}
private static void minHeapFixdown(int[] a, int i, int n) {
    int t = a[i], j = 2*i + 1;
    while (j < n) {
        if (j+1 < n && a[j+1] < a[j]) j++;
        if (a[j] >= t) break;
        a[i] = a[j]; i = j; j = 2*i + 1;
    }
    a[i] = t;
}

7. 冒泡排序

核心思想

相鄰比較，大的後移，像氣泡上浮。

代碼

public static void bubbleSort(int[] a) {
    for (int i = 0; i < a.length; i++)
        for (int j = 0; j < a.length - i - 1; j++)
            if (a[j+1] < a[j]) { int t = a[j]; a[j] = a[j+1]; a[j+1] = t; }
}

選型指南

• 小數據量（<50）或近乎有序 → 插入排序；
• 通用高效、原地排序 → 快速排序（隨機化基準避免最壞）；
• 需穩定、外部排序、鏈表排序 → 歸並排序；
• 嚴格 O(n log n) 最壞保證、原地 → 堆排序；
• 教學/極小數據 → 冒泡/選擇；
• 工程實際建議：直接用 Arrays.sort()（雙軸快排 + 歸並混合）或 Collections.sort()（TimSort）。