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

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

快速排序工作原理

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

步驟 1：選擇樞軸元素

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

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

我們將樞軸元素放置在其大於它的元素之前，小於它的元素之後。為此，我們將遍歷數(shù)組，並將樞軸與它之前的每個(gè)元素進(jìn)行比較。如果找到一個(gè)大於樞軸的元素，我們?yōu)樗⒁粋€(gè)第二個(gè)指標(biāo)：

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

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

繼續(xù)此過程直到到達(dá)陣列的末端：

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

步驟 3：分割數(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í)作

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 方法：先呼叫 partition 方法將陣列分成兩個(gè)子數(shù)組，然後遞歸呼叫 quickSort 對(duì)左右子數(shù)組進(jìn)行排序。這個(gè)過程持續(xù)進(jìn)行，直到所有子數(shù)組都只包含一個(gè)元素，此時(shí)數(shù)組已排序。

partition 方法：負(fù)責(zé)將陣列分成兩個(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í)間複雜度

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

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

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

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

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