Java 八大排序演算法完整實作與複雜度比較

Java 排序演算法大全：分類、複雜度、穩定性與完整程式碼

本文整理 Java 常見 8 大排序演算法，涵蓋插入、交換、選擇、歸並、分配五大類，提供完整可執行程式碼、時間/空間複雜度分析、穩定性判斷與適用場景建議。

演算法分類與複雜度總表

核心演算法完整實作

1. 直接插入排序

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

2. 希爾排序

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

3. 氣泡排序（優化版）

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

4. 快速排序（單向掃描分區）

public static void quickSort(int[] data) {
    quick(data, 0, data.length - 1);
}
private static void quick(int[] a, int low, int high) {
    if (low < high) {
        int pivot = partition(a, low, high);
        quick(a, low, pivot - 1);
        quick(a, pivot + 1, high);
    }
}
private static int partition(int[] a, int low, int high) {
    int pivot = a[low];
    while (low < high) {
        while (low < high && a[high] >= pivot) high--;
        a[low] = a[high];
        while (low < high && a[low] <= pivot) low++;
        a[high] = a[low];
    }
    a[low] = pivot;
    return low;
}

5. 直接選擇排序

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

6. 堆積排序

public static void heapSort(int[] data) {
    int n = data.length;
    // 建立大根堆
    for (int i = n / 2 - 1; i >= 0; i--) heapify(data, n, i);
    // 逐一取出堆頂
    for (int i = n - 1; i > 0; i--) {
        int tmp = data[0]; data[0] = data[i]; data[i] = tmp;
        heapify(data, i, 0);
    }
}
private static void heapify(int[] a, int n, int i) {
    int largest = i;
    int l = 2*i+1, r = 2*i+2;
    if (l < n && a[l] > a[largest]) largest = l;
    if (r < n && a[r] > a[largest]) largest = r;
    if (largest != i) {
        int tmp = a[i]; a[i] = a[largest]; a[largest] = tmp;
        heapify(a, n, largest);
    }
}

7. 歸並排序

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

8. 基數排序（LSD，針對非負整數）

public static void radixSort(int[] data) {
    int max = Arrays.stream(data).max().orElse(0);
    for (int exp = 1; max / exp > 0; exp *= 10) {
        int[] output = new int[data.length];
        int[] count = new int[10];
        for (int v : data) count[(v / exp) % 10]++;
        for (int i = 1; i < 10; i++) count[i] += count[i-1];
        for (int i = data.length - 1; i >= 0; i--)
            output[--count[(data[i] / exp) % 10]] = data[i];
        System.arraycopy(output, 0, data, 0, data.length);
    }
}

選擇指南

• 資料量 < 50：插入排序最快、程式碼最簡。
• 一般通用、追求平均效能：快速排序（Arrays.sort() 內部用雙軸快排）。
• 需穩定排序：歸並排序（Arrays.sort(Object[]) 使用 TimSort，穩定）。
• 記憶體極度受限：堆積排序（O(1) 空間）。
• 整數、範圍已知：基數排序（線性時間）。