深入剖析 Java 快速排序算法

快速排序（Quick Sort）是一種高效的排序算法，其平均時(shí)間復(fù)雜度為 O(n log n)，最壞情況下為 O(n^2)。它采用分治策略，將待排序數(shù)組遞歸地劃分成更小的子數(shù)組，直到子數(shù)組長(zhǎng)度為 1 或 0，此時(shí)子數(shù)組已經(jīng)有序。

算法步驟

快速排序算法的核心步驟如下：

1. 選擇基準(zhǔn)值（Pivot）：從數(shù)組中選擇一個(gè)元素作為基準(zhǔn)值，通常選擇第一個(gè)、最后一個(gè)或中間的元素。
2. 分區(qū)（Partition）：將數(shù)組中小于基準(zhǔn)值的元素放到基準(zhǔn)值左邊，大于基準(zhǔn)值的元素放到基準(zhǔn)值右邊。
3. 遞歸排序：對(duì)基準(zhǔn)值左右兩邊的子數(shù)組分別遞歸執(zhí)行步驟 1 和步驟 2，直到子數(shù)組長(zhǎng)度為 1 或 0。

Java 代碼實(shí)現(xiàn)

以下是一個(gè) Java 代碼示例，演示了如何使用快速排序算法對(duì)整數(shù)數(shù)組進(jìn)行排序：

public class QuickSort {

    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // 分區(qū)操作，將數(shù)組分為兩部分
            int pivotIndex = partition(arr, low, high);

            // 遞歸排序兩個(gè)子數(shù)組
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        // 選擇最后一個(gè)元素作為基準(zhǔn)值
        int pivot = arr[high]; 
        int i = (low - 1); 

        for (int j = low; j < high; j++) {
            // 如果當(dāng)前元素小于等于基準(zhǔn)值
            if (arr[j] <= pivot) {
                i++;

                // 交換 arr[i] 和 arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // 交換 arr[i+1] 和 arr[high] (或基準(zhǔn)值)
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        int n = arr.length;

        quickSort(arr, 0, n - 1);

        System.out.println("排序后的數(shù)組:");
        for (int i = 0; i < n; ++i) {
            System.out.print(arr[i] + " ");
        }
    }
}

算法分析

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

• 最佳情況：O(n log n)，當(dāng)每次分區(qū)操作都能將數(shù)組分成大小相等的兩個(gè)子數(shù)組時(shí)。
• 平均情況：O(n log n)
• 最壞情況：O(n^2)，當(dāng)數(shù)組已經(jīng)有序或逆序時(shí)，每次分區(qū)操作都會(huì)將數(shù)組分成一個(gè)大小為 n-1 的子數(shù)組和一個(gè)大小為 1 的子數(shù)組。

空間復(fù)雜度:

• 最佳情況：O(log n)，遞歸調(diào)用棧的深度。
• 最壞情況：O(n)，遞歸調(diào)用棧的深度。

優(yōu)缺點(diǎn)

優(yōu)點(diǎn):

• 高效的平均時(shí)間復(fù)雜度。
• 原地排序，不需要額外的存儲(chǔ)空間。

缺點(diǎn):

• 最壞情況下的時(shí)間復(fù)雜度較高。
• 不穩(wěn)定排序，相同元素的相對(duì)位置可能會(huì)改變。

應(yīng)用場(chǎng)景

快速排序算法適用于以下場(chǎng)景：

• 對(duì)大型數(shù)據(jù)集進(jìn)行排序。
• 對(duì)數(shù)據(jù)進(jìn)行部分排序。
• 在其他算法中作為子程序使用。

總結(jié)

快速排序是一種高效的排序算法，它易于實(shí)現(xiàn)且在大多數(shù)情況下表現(xiàn)良好。了解其工作原理、優(yōu)缺點(diǎn)和應(yīng)用場(chǎng)景可以幫助開(kāi)發(fā)者在實(shí)際應(yīng)用中選擇合適的排序算法。