Java 快速排序演算法完整實作與核心原理解析

快速排序演算法概述

快速排序是對冒泡排序的一種重大改良，由 C. A. R. Hoare 於 1962 年提出。這是一種基於分治法的高效排序演算法，平均時間複雜度為 O(n log n)，是實務應用中最常用的排序方法之一。

核心演算法思想

快速排序的核心思路是：通過一趟排序將待排序數據分割成獨立的兩部分，其中一部分的所有數據都比另一部分的所有數據要小，然後對這兩部分數據分別進行快速排序，整個排序過程遞歸進行，最終使整個數據變成有序序列。

詳細實作步驟

1. 選擇基準值：以第一個關鍵字作為基準值，將陣列分成兩個子區
2. 分區操作：使左區所有關鍵字小於等於基準值，右區所有關鍵字大於等於基準值，基準值最終位於兩個子區中間的適當位置
3. 遞歸處理：把左區作為一個整體，用相同方法處理，右區進行相同處理
4. 終止條件：重複上述步驟，直到左右子區都處理完畢

Java 程式碼實作

public static void quickSortByMid(int[] a, int low, int high) {
    if (low >= high) return;
    
    // 分區邏輯
    int pivot = a[low]; // 基準值
    int i = low, j = high;
    
    while (i < j) {
        // 從右向左找第一個小於基準值的元素
        while (i < j && a[j] >= pivot) --j;
        a[i] = a[j];
        
        // 從左向右找第一個大於基準值的元素
        while (i < j && a[i] <= pivot) ++i;
        a[j] = a[i];
    }
    
    a[i] = pivot; // 基準值歸位
    
    // 遞歸排序左右子區
    quickSortByMid(a, low, i - 1);
    quickSortByMid(a, i + 1, high);
}

效能特性與優化建議

快速排序在大多數情況下表現優異，但最壞情況（如已有序陣列）時間複雜度會退化到 O(n²)。常見優化策略包括：

• 三數取中法選擇基準值
• 小區間改用插入排序
• 隨機化基準值選擇
• 尾遞歸優化

掌握快速排序不僅是演算法面試的必考題，更是理解分治法思想的絕佳切入點。