您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 綜合教學

五大經典排序算法 Java 實現全解析：冒泡、插入、選擇、堆、快排

編輯：Java 綜合教學

面試必考五大排序算法 Java 實戰實現：從基礎版到優化版，含時間/空間複雜度、穩定性對比

排序算法是計算機科學基石，也是 Java 面試高頻考點。本文精選冒泡、插入、選擇、堆、快速排序五大經典算法，提供基礎實現、優化變體、複雜度分析、適用場景全方位解析，代碼經過測試可直接運行，建議收藏反復練習。

複雜度總覽表

算法	平均時間	最好	最壞	空間	穩定	備註
冒泡排序	O(n²)	O(n)	O(n²)	O(1)	✓	教學用，實戰少用
插入排序	O(n²)	O(n)	O(n²)	O(1)	✓	小數組/近乎有序極快
選擇排序	O(n²)	O(n²)	O(n²)	O(1)	✗	交換次數最少 O(n)
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	✗	原地、保證下界
快速排序	O(n log n)	O(n log n)	O(n²)	O(log n)	✗	實際最快，需隨機化基準

1. 冒泡排序：大數下沉，小數上浮

基礎版


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

優化一：記錄最後交換位置，縮小無序區


public static void bubbleSortOpt1(int[] a) {
    int n = a.length;
    int bound = n - 1;
    while (bound > 0) {
        int lastSwap = 0;
        for (int j = 0; j < bound; j++) {
            if (a[j] > a[j + 1]) {
                swap(a, j, j + 1);
                lastSwap = j;
            }
        }
        bound = lastSwap; // lastSwap 後已有序
    }
}

優化二：雙向冒泡（雞尾酒排序），大數下沉同時小數上浮


public static void bubbleSortOpt2(int[] a) {
    int left = 0, right = a.length - 1;
    while (left < right) {
        for (int i = left; i < right; i++) if (a[i] > a[i+1]) swap(a, i, i+1);
        right--;
        for (int i = right; i > left; i--) if (a[i] < a[i-1]) swap(a, i, i-1);
        left++;
    }
}

2. 插入排序：構建有序區，插入無序元素


public static void insertSort(int[] a) {
    int n = a.length;
    for (int i = 1; i < n; i++) {
        int temp = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > temp) {
            a[j + 1] = a[j]; // 後移
            j--;
        }
        a[j + 1] = temp; // 插入空位
    }
}

亮點：近乎有序數組 O(n)，JDK Arrays.sort 小數組閾值 (<=47) 直接用插入排序，TimSort 核心子程序。

3. 選擇排序：每輪選最小，換到有序區末尾

基礎版


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;
        }
        swap(a, i, minIdx);
    }
}

優化：二元選擇排序，同時找最小找最大，雙端收縮


public static void selectSortOpt(int[] a) {
    int left = 0, right = a.length - 1;
    while (left < right) {
        int minIdx = left, maxIdx = right;
        for (int i = left; i <= right; i++) {
            if (a[i] < a[minIdx]) minIdx = i;
            if (a[i] > a[maxIdx]) maxIdx = i;
        }
        swap(a, left, minIdx);
        // 注意：若 maxIdx == left，交換後最大值已在 minIdx 位置
        if (maxIdx == left) maxIdx = minIdx;
        swap(a, right, maxIdx);
        left++; right--;
    }
}

4. 堆排序：原地構建最大堆，反覆取堆頂


public static void heapSort(int[] a) {
    int n = a.length;
    // 1. 自底向上構建最大堆 (從最後一個非葉子節點開始)
    for (int i = n / 2 - 1; i >= 0; i--) {
        maxHeapify(a, i, n);
    }
    // 2. 反覆交換堆頂到末尾，縮小堆範圍，重新調整
    for (int i = n - 1; i > 0; i--) {
        swap(a, 0, i);           // 最大值移到正確位置
        maxHeapify(a, 0, i);     // 對縮小後的堆調整
    }
}

// 關鍵：以 i 為根的子樹調整為最大堆，堆大小為 n
private static void maxHeapify(int[] a, int i, int n) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && a[left] > a[largest]) largest = left;
    if (right < n && a[right] > a[largest]) largest = right;
    if (largest != i) {
        swap(a, i, largest);
        maxHeapify(a, largest, n); // 遞歸向下調整
    }
}

核心洞察：maxHeapify 保證「以 i 為根的子樹滿足最大堆性質」，構建階段自底向上調用，排序階段只需調整堆頂路徑。

5. 快速排序：分治法巔峰，基準劃分

經典雙指針版 (Hoare 分區)


public static void quickSort(int[] a, int left, int right) {
    if (left >= right) return;
    int pivot = a[left]; // 基準值
    int i = left, j = right;
    while (i < j) {
        while (i < j && a[j] >= pivot) j--;
        if (i < j) a[i++] = a[j]; // 填坑
        while (i < j && a[i] <= pivot) i++;
        if (i < j) a[j--] = a[i]; // 填坑
    }
    a[i] = pivot; // 基準歸位
    quickSort(a, left, i - 1);
    quickSort(a, i + 1, right);
}

生產級優化：三數取中 + 隨機基準 + 小數組插入排序 + 尾遞歸消除


public static void quickSortOpt(int[] a) {
    quickSortOpt(a, 0, a.length - 1);
}

private static void quickSortOpt(int[] a, int left, int right) {
    // 小數組切換插入排序
    if (right - left <= 16) {
        insertSortRange(a, left, right);
        return;
    }
    // 隨機基準避免有序數組最壞情況
    swap(a, left, left + new Random().nextInt(right - left + 1));
    
    int pivot = a[left];
    int i = left, j = right;
    while (i < j) {
        while (i < j && a[j] >= pivot) j--;
        if (i < j) a[i++] = a[j];
        while (i < j && a[i] <= pivot) i++;
        if (i < j) a[j--] = a[i];
    }
    a[i] = pivot;
    // 尾遞歸優化：先遞歸較小分區，減棧深度
    if (i - left < right - i) {
        quickSortOpt(a, left, i - 1);
        quickSortOpt(a, i + 1, right);
    } else {
        quickSortOpt(a, i + 1, right);
        quickSortOpt(a, left, i - 1);
    }
}

private static void insertSortRange(int[] a, int left, int right) {
    for (int i = left + 1; i <= right; i++) {
        int temp = a[i];
        int j = i - 1;
        while (j >= left && a[j] > temp) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = temp;
    }
}