算法入門排序算法：快速排序

一、什么是快速排序？

快速排序（Quick Sort）是由英國計算機科學家托尼·霍爾（Tony Hoare）于1959年發明的一種高效的排序算法。它采用了分治策略（Divide and Conquer），被譽為"二十世紀十大算法"之一，是目前實際應用中最快的通用排序算法。

快速排序的核心思想可以概括為："挑一個元素，小的放左邊，大的放右邊，遞歸處理"。這種策略使得快速排序在平均情況下具有優異的性能表現。

二、快速排序的工作原理

快速排序的基本思想可以分為三個步驟：

選擇基準（Pivot）：從數組中選擇一個元素作為基準
分區操作（Partitioning）：重新排列數組，使所有小于基準的元素都在基準左邊，所有大于基準的元素都在基準右邊
遞歸排序：遞歸地對基準左右兩邊的子數組進行快速排序

這個過程就像是在整理書架：先選一本書作為參考，把所有比它薄的書放左邊，比它厚的書放右邊，然后對左右兩堆書分別重復這個過程。

三、快速排序的Java實現

下面是快速排序的完整Java實現，包含多種基準選擇策略：

import java.util.Arrays;
import java.util.Random;

public class QuickSort {
    
    // 快速排序主方法
    public static void quickSort(int[] array, int low, int high) {
        if (low < high) {
            // 分區操作，返回基準的最終位置
            int pivotIndex = partition(array, low, high);

            // 遞歸排序左半部分
            quickSort(array, low, pivotIndex - 1);
            // 遞歸排序右半部分
            quickSort(array, pivotIndex + 1, high);
        }
    }

    // 分區方法 - 使用最后一個元素作為基準
    private static int partition(int[] array, int low, int high) {
        // 選擇最后一個元素作為基準
        int pivot = array[high];
        int i = low - 1; // 小于基準的元素的邊界索引

        for (int j = low; j < high; j++) {
            // 如果當前元素小于或等于基準
            if (array[j] <= pivot) {
                i++;
                // 交換array[i]和array[j]
                swap(array, i, j);
            }
        }

        // 將基準放到正確位置
        swap(array, i + 1, high);
        return i + 1;
    }

    // 隨機化快速排序的分區方法
    private static int randomizedPartition(int[] array, int low, int high) {
        // 隨機選擇基準
        Random random = new Random();
        int randomIndex = low + random.nextInt(high - low + 1);
        swap(array, randomIndex, high); // 將隨機選擇的基準移到末尾

        return partition(array, low, high);
    }

    // 三數取中法選擇基準
    private static int medianOfThreePartition(int[] array, int low, int high) {
        int mid = low + (high - low) / 2;

        // 對左、中、右三個數進行排序
        if (array[low] > array[mid]) swap(array, low, mid);
        if (array[low] > array[high]) swap(array, low, high);
        if (array[mid] > array[high]) swap(array, mid, high);

        // 將中位數放到high-1位置
        swap(array, mid, high - 1);
        return partition(array, low + 1, high - 1);
    }

    // 交換數組中的兩個元素
    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    // 打印數組的輔助方法
    private static void printArray(String message, int[] array, int low, int high) {
        System.out.print(message + ": [");
        for (int i = low; i <= high; i++) {
            System.out.print(array[i]);
            if (i < high) System.out.print(", ");
        }
        System.out.println("]");
    }

    public static void main(String[] args) {
        int[] data = {10, 7, 8, 9, 1, 5, 3, 6, 4, 2};
        System.out.println("原始數組: " + Arrays.toString(data));

        // 復制數組用于不同的排序測試
        int[] data1 = Arrays.copyOf(data, data.length);
        int[] data2 = Arrays.copyOf(data, data.length);

        // 標準快速排序
        quickSort(data1, 0, data1.length - 1);
        System.out.println("快速排序結果: " + Arrays.toString(data1));

        // 隨機化快速排序
        quickSortRandomized(data2, 0, data2.length - 1);
        System.out.println("隨機化快速排序結果: " + Arrays.toString(data2));
    }

    // 隨機化快速排序版本
    public static void quickSortRandomized(int[] array, int low, int high) {
        if (low < high) {
            int pivotIndex = randomizedPartition(array, low, high);
            quickSortRandomized(array, low, pivotIndex - 1);
            quickSortRandomized(array, pivotIndex + 1, high);
        }
    }
}

代碼解析：

分區過程：
- 選擇基準元素（通常選擇最后一個元素）
- 使用雙指針技術重新排列數組
- 保證基準左邊的元素都小于等于基準，右邊的元素都大于基準
遞歸排序：
- 對基準左右兩邊的子數組遞歸調用快速排序
- 基準元素已經在正確位置，不需要再參與排序
優化策略：
- 隨機化選擇基準：避免最壞情況發生
- 三數取中法：選擇左、中、右三個元素的中位數作為基準
- 小數組優化：對小規模子數組使用插入排序

四、快速排序的性能分析

時間復雜度：

最壞情況：O(n2) —— 當每次選擇的基準都是最大或最小元素時
最好情況：O(n log n) —— 每次分區都能均勻劃分
平均情況：O(n log n)

空間復雜度：

遞歸調用棧：O(log n)（平均情況）到 O(n)（最壞情況）
原地排序：不需要額外的存儲空間

穩定性：

基本快速排序是不穩定的排序算法，因為分區過程中的交換可能改變相等元素的相對順序。

五、快速排序的優缺點

優點：

平均情況下效率極高，是實際應用中最快的排序算法
原地排序，空間效率高
緩存友好，具有良好的引用局部性
易于并行化處理

缺點：

最壞情況下性能較差（O(n2)）
不穩定排序
遞歸實現可能導致棧溢出
對于小規模數據，可能不如簡單排序算法高效

六、快速排序的實際應用

快速排序因其優異的平均性能被廣泛應用于：

編程語言標準庫：Java的Arrays.sort()、C++的std::sort()等都使用快速排序的變體
數據庫系統：用于查詢結果的排序和索引構建
操作系統：文件系統排序、進程調度等
科學計算：大規模數據分析和處理
競賽編程：由于實現簡單且效率高，是算法競賽中的常用選擇

七、快速排序的變體和優化

雙軸快速排序：使用兩個基準進行分區，Java Arrays.sort()采用此方法
三路快速排序：處理大量重復元素時更高效，將數組分為小于、等于、大于基準三部分
內省排序：結合快速排序、堆排序和插入排序的優點，避免最壞情況
尾遞歸優化：減少遞歸調用棧的深度
并行快速排序：利用多核處理器并行處理子數組

八、快速排序的數學原理

快速排序的性能分析基于遞歸關系：
T(n) = T(k) + T(n-k-1) + O(n)

其中k是分區后左子數組的大小。平均情況下，k ≈ n/2，因此：
T(n) = 2T(n/2) + O(n) = O(n log n)

這種遞歸關系體現了分治策略的精髓：將大問題分解為小問題，分別解決后再合并結果。

九、總結

快速排序以其卓越的平均性能和簡潔的實現，成為了計算機科學中最重要、最實用的算法之一。托尼·霍爾因其貢獻獲得了圖靈獎，這充分說明了快速排序在計算機科學中的地位。

理解快速排序不僅有助于掌握分治策略這一重要的算法設計范式，還能深入理解遞歸、時間復雜度分析等計算機科學核心概念。在實際編程中，雖然我們通常使用語言內置的排序函數，但了解其底層原理對于寫出高效、可靠的代碼至關重要。

正如計算機科學家Jon Bentley所說："快速排序是最美麗的算法之一，它簡潔、高效，而且實用。"掌握快速排序，是每個程序員算法學習道路上的重要里程碑。

posted @ 2025-08-20 21:03 高級摸魚工程師閱讀(185) 評論(0) 收藏舉報

刷新頁面返回頂部

famous-oneday