QuickSort 算法詳解：高效的排序利器

快速排序 (QuickSort) 是一種基于分治策略的高效排序算法。分治法將問題分解成更小的子問題，分別解決這些子問題，然后組合子問題的解得到最終解。在快速排序中，數(shù)組通過選擇一個(gè)分區(qū)元素來(lái)劃分，該元素決定數(shù)組的分割點(diǎn)。在劃分之前，分區(qū)元素的位置會(huì)重新排列，使其位于大于它的元素之前，小于它的元素之后。左右子數(shù)組將以這種方式遞歸劃分，直到每個(gè)子數(shù)組只包含一個(gè)元素，此時(shí)數(shù)組已排序。

快速排序工作原理

讓我們以升序排序以下數(shù)組為例：

步驟 1：選擇樞軸元素

我們選擇最后一個(gè)元素作為樞軸：

步驟 2：重新排列樞軸元素

我們將樞軸元素放置在其大于它的元素之前，小于它的元素之后。為此，我們將遍歷數(shù)組，并將樞軸與它之前的每個(gè)元素進(jìn)行比較。如果找到一個(gè)大于樞軸的元素，我們?yōu)樗鼊?chuàng)建一個(gè)第二個(gè)指針：

如果找到一個(gè)小于樞軸的元素，我們將它與第二個(gè)指針交換：

重復(fù)此過程，將下一個(gè)大于樞軸的元素設(shè)置為第二個(gè)指針，如果找到小于樞軸的元素則進(jìn)行交換：

繼續(xù)此過程直到到達(dá)數(shù)組的末尾：

完成元素比較后，小于樞軸的元素已移動(dòng)到右側(cè)，然后我們將樞軸與第二個(gè)指針交換：

步驟 3：劃分?jǐn)?shù)組

根據(jù)分區(qū)索引劃分?jǐn)?shù)組。如果我們將數(shù)組表示為 arr[start..end]，則通過分區(qū)劃分?jǐn)?shù)組，可以得到左子數(shù)組 arr[start..partitionIndex-1] 和右子數(shù)組 arr[partitionIndex 1..end]。

以這種方式繼續(xù)劃分子數(shù)組，直到每個(gè)子數(shù)組只包含一個(gè)元素：

此時(shí)，數(shù)組已排序。

快速排序代碼實(shí)現(xiàn)

import java.util.Arrays;

public class QuickSortTest {
    public static void main(String[] args){
        int[] arr = {8, 6, 2, 3, 9, 4};
        System.out.println("未排序數(shù)組: " + Arrays.toString(arr));
        quickSort(arr, 0, arr.length-1);
        System.out.println("已排序數(shù)組: " + Arrays.toString(arr));
    }

    public static int partition(int[] arr, int start, int end){
        // 將最后一個(gè)元素設(shè)置為樞軸
        int pivot = arr[end];
        // 創(chuàng)建指向下一個(gè)較大元素的指針
        int secondPointer = start-1;

        // 將小于樞軸的元素移動(dòng)到樞軸左側(cè)
        for (int i = start; i < end; i++){
            if (arr[i] < pivot){
                secondPointer++;
                // 交換元素
                int temp = arr[secondPointer];
                arr[secondPointer] = arr[i];
                arr[i] = temp;
            }
        }
        // 將樞軸與第二個(gè)指針交換
        int temp = arr[secondPointer+1];
        arr[secondPointer+1] = arr[end];
        arr[end] = temp;
        // 返回分區(qū)索引
        return secondPointer+1;
    }

    public static void quickSort(int[] arr, int start, int end){
        if (start < end){
            // 找到分區(qū)索引
            int partitionIndex = partition(arr, start, end);
            // 遞歸調(diào)用快速排序
            quickSort(arr, start, partitionIndex-1);
            quickSort(arr, partitionIndex+1, end);
        }
    }
}

代碼解讀

quickSort 方法：首先調(diào)用 partition 方法將數(shù)組分成兩個(gè)子數(shù)組，然后遞歸調(diào)用 quickSort 對(duì)左右子數(shù)組進(jìn)行排序。這個(gè)過程持續(xù)進(jìn)行，直到所有子數(shù)組都只包含一個(gè)元素，此時(shí)數(shù)組已排序。

partition 方法：負(fù)責(zé)將數(shù)組分成兩個(gè)子數(shù)組。它首先設(shè)置樞軸和下一個(gè)較大元素的指針，然后遍歷數(shù)組，將小于樞軸的元素移動(dòng)到左側(cè)。之后，它將樞軸與第二個(gè)指針交換，并返回分區(qū)位置。

運(yùn)行以上代碼，控制臺(tái)將輸出以下內(nèi)容：

未排序數(shù)組: [8, 6, 2, 3, 9, 4] 已排序數(shù)組: [2, 3, 4, 6, 8, 9]

時(shí)間復(fù)雜度

最佳情況 (O(n log n))：當(dāng)樞軸每次都將數(shù)組分成兩個(gè)幾乎相等的部分時(shí)，就會(huì)出現(xiàn)最佳情況。

平均情況 (O(n log n))：在平均情況下，樞軸將數(shù)組分成兩個(gè)不相等的部分，但遞歸深度和比較次數(shù)仍然與 n log n 成正比。

最壞情況 (O(n2))：當(dāng)樞軸始終將數(shù)組分成非常不相等的部分（例如，一部分只有一個(gè)元素，另一部分有 n-1 個(gè)元素）時(shí)，就會(huì)出現(xiàn)最壞情況。例如，當(dāng)排序一個(gè)逆序數(shù)組時(shí)，并且樞軸選擇不佳時(shí)，就會(huì)發(fā)生這種情況。

空間復(fù)雜度 (O(log n))：快速排序通常就地實(shí)現(xiàn)，不需要額外的數(shù)組。

以上是了解快速排序算法（附Java示例）的詳細(xì)內(nèi)容。更多信息請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！