App下載

深入剖析 Java 快速排序算法

蔡文姬腿堡 2024-06-04 11:51:13 瀏覽數(shù) (768)
反饋

1f9a40dbe41b3ddeedefdf55d6568897

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

算法步驟

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

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

Java 代碼實現(xiàn)

以下是一個 Java 代碼示例,演示了如何使用快速排序算法對整數(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);

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

    private static int partition(int[] arr, int low, int high) {
        // 選擇最后一個元素作為基準(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] + " ");
        }
    }
}

算法分析

時間復(fù)雜度:

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

空間復(fù)雜度:

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

優(yōu)缺點

優(yōu)點:

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

缺點:

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

應(yīng)用場景

快速排序算法適用于以下場景:

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

總結(jié)

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


0 人點贊