快速排序的基本概念：

快速排序的核心就是選擇一個(gè)基準(zhǔn)值，然后將數(shù)組分成兩部分：

• 左邊：比基準(zhǔn)值小的元素。
• 右邊：比基準(zhǔn)值大的元素。 然后遞歸地對(duì)左右兩部分繼續(xù)進(jìn)行這個(gè)過(guò)程，直到每部分都排好序。

來(lái)，我們用現(xiàn)實(shí)生活中的例子來(lái)理解！

假設(shè)你在整理一堆數(shù)字卡片??，你想把這些卡片按從小到大的順序排列?？焖倥判蚓拖袷悄阏驹谧雷优赃?，對(duì)這些卡片進(jìn)行一次大分揀??，然后不斷地把小卡片和大卡片分成左右兩邊，直到它們都排好位置。

舉個(gè)具體的例子：

你有這樣一堆數(shù)字：
[8, 3, 5, 1, 9, 6]

第一步：選一個(gè)基準(zhǔn)值（pivot）

我們從中間選一個(gè)數(shù)字作為基準(zhǔn)值，比如選擇 6 作為基準(zhǔn)。

第二步：分揀

• 比6小的數(shù)字放到左邊，即：[3, 5, 1]
• 比6大的數(shù)字放到右邊，即：[8, 9]
• 基準(zhǔn)值6就放在中間。

現(xiàn)在我們有了這樣的分揀結(jié)果： 左邊：[3, 5, 1], 中間：6, 右邊：[8, 9]

第三步：遞歸處理左邊和右邊

• 對(duì)左邊的數(shù)組 [3, 5, 1] 再次進(jìn)行快速排序：

  • 選擇基準(zhǔn)值：3
  • 左邊：[1] （比3?。?/li>
  • 右邊：[5] （比3大）

  現(xiàn)在左邊排好了：[1, 3, 5]

• 右邊的數(shù)組 [8, 9]：

  • 這個(gè)部分已經(jīng)排好了，因?yàn)?比9小。

第四步：組合結(jié)果

現(xiàn)在我們把所有部分組合起來(lái)：

• 左邊：[1, 3, 5]
• 基準(zhǔn)值：6
• 右邊：[8, 9]

最終得到的排序結(jié)果就是：
[1, 3, 5, 6, 8, 9]

簡(jiǎn)單總結(jié)快速排序的步驟：

• 選擇基準(zhǔn)值：選一個(gè)數(shù)字作為基準(zhǔn)值，通常選擇數(shù)組中的某個(gè)元素。
• 分揀：把比基準(zhǔn)值小的放左邊，比基準(zhǔn)值大的放右邊。
• 遞歸：對(duì)左邊和右邊的部分繼續(xù)進(jìn)行相同的操作。
• 組合結(jié)果：最終把排好序的部分拼在一起。

用生活中的例子來(lái)理解：

Imagine 你要整理一個(gè)大抽屜里的襪子??。你先挑出一只作為“基準(zhǔn)襪”，比如中等長(zhǎng)度的，然后開(kāi)始整理：

• 比基準(zhǔn)襪短的放一邊（左邊）。
• 比基準(zhǔn)襪長(zhǎng)的放另一邊（右邊）。

接著你再分別整理兩邊的襪子，按照同樣的方式繼續(xù)分揀，直到所有的襪子都按長(zhǎng)短排好順序！

快速排序的優(yōu)勢(shì)

快速排序的效率很高，因?yàn)樗看味紝?wèn)題規(guī)模減半。通過(guò)把問(wèn)題分解成小問(wèn)題，它能快速解決排序問(wèn)題。平均時(shí)間復(fù)雜度是 O(n log n)，在大多數(shù)情況下比冒泡排序（時(shí)間復(fù)雜度 O(n²)）要快得多。

快速排序的完整Java代碼：

public class QuickSortExample {

    // 快速排序的主方法，傳入數(shù)組、最小索引和最大索引
    public static void quickSort(int[] arr, int low, int high) {
        // 如果低索引小于高索引，說(shuō)明數(shù)組還沒(méi)排序完
        if (low < high) {
            // 找到基準(zhǔn)元素的位置，并把數(shù)組分成兩部分
            int pivotIndex = partition(arr, low, high);
            
            // 遞歸地對(duì)基準(zhǔn)左邊部分進(jìn)行快速排序
            quickSort(arr, low, pivotIndex - 1);
            // 遞歸地對(duì)基準(zhǔn)右邊部分進(jìn)行快速排序
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    // 分區(qū)方法：選擇一個(gè)基準(zhǔn)值，把小于基準(zhǔn)的元素放在左邊，大于基準(zhǔn)的放在右邊
    private static int partition(int[] arr, int low, int high) {
        // 選擇最右邊的元素作為基準(zhǔn)
        int pivot = arr[high];
        
        // i是用來(lái)追蹤小于基準(zhǔn)值的元素的位置
        int i = low - 1; 

        // 遍歷數(shù)組，找到所有小于基準(zhǔn)值的元素
        for (int j = low; j < high; j++) {
            // 如果當(dāng)前元素小于或等于基準(zhǔn)值
            if (arr[j] <= pivot) {
                i++; // 增加i，準(zhǔn)備交換小元素的位置
                
                // 交換arr[i]和arr[j]，把小元素放到前面
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // 最后，把基準(zhǔn)值放到正確的位置（中間）
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        // 返回基準(zhǔn)值的正確位置
        return i + 1;
    }

    // 測(cè)試快速排序方法的主函數(shù)
    public static void main(String[] args) {
        // 定義一個(gè)需要排序的數(shù)組
        int[] arr = {8, 3, 5, 1, 9, 6};

        // 打印排序前的數(shù)組
        System.out.println("排序前的數(shù)組：");
        printArray(arr);

        // 調(diào)用快速排序方法，排序整個(gè)數(shù)組
        quickSort(arr, 0, arr.length - 1);

        // 打印排序后的數(shù)組
        System.out.println("排序后的數(shù)組：");
        printArray(arr);
    }

    // 輔助方法：打印數(shù)組中的所有元素
    private static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

代碼詳解：

• quickSort 方法：這是快速排序的主方法。它接收一個(gè)數(shù)組、最小索引（low）和最大索引（high）。如果當(dāng)前子數(shù)組的大小大于1（low < high），它會(huì)找到基準(zhǔn)值的正確位置，然后遞歸地排序左右兩部分。
• partition 方法：這個(gè)方法的作用是將數(shù)組分成兩部分：
  • 左邊是比基準(zhǔn)值小或相等的元素。
  • 右邊是比基準(zhǔn)值大的元素。
    它返回的是基準(zhǔn)值最終所在的位置，這樣我們知道從哪里把數(shù)組一分為二。
• printArray 方法：這個(gè)方法是一個(gè)輔助方法，用來(lái)打印數(shù)組內(nèi)容，方便我們查看排序前后的效果。

解釋這個(gè)例子的通俗版本：

• 選基準(zhǔn)值：
  比如我們從數(shù)組 [8, 3, 5, 1, 9, 6] 中選了 6 作為基準(zhǔn)值。這個(gè)基準(zhǔn)值就像是一條“分界線”，我們要把小于 6 的元素放到左邊，把大于 6 的元素放到右邊。
• 分左右：
  遍歷數(shù)組，依次將小于 6 的元素放在數(shù)組的前面，大于 6 的元素放到數(shù)組的后面。比如 3, 5, 和 1 會(huì)被移到前面，8, 9 會(huì)放到后面，6 作為基準(zhǔn)值就在中間。
• 遞歸處理：
  然后我們對(duì)左邊部分 [3, 5, 1] 和右邊部分 [8, 9] 繼續(xù)做相同的分揀，直到每個(gè)部分都只有一個(gè)元素為止。
• 排序完成：
  最后，所有的元素就按照從小到大的順序排好了，結(jié)果是 [1, 3, 5, 6, 8, 9]。

排序前的數(shù)組：
8 3 5 1 9 6 
排序后的數(shù)組：
1 3 5 6 8 9 

小結(jié)：

• 快速排序通過(guò)挑選一個(gè)基準(zhǔn)值，然后將數(shù)組分為兩部分：左邊比基準(zhǔn)小，右邊比基準(zhǔn)大。
• 然后對(duì)左右兩部分繼續(xù)遞歸進(jìn)行快速排序，直到數(shù)組排序完畢。
• 整個(gè)過(guò)程其實(shí)就是不停地“分揀”元素，類似于你把大小不同的物品進(jìn)行快速分揀，最后得到排序結(jié)果。

總結(jié) 

到此這篇關(guān)于Java快速排序?qū)崿F(xiàn)的文章就介紹到這了,更多相關(guān)Java快速排序?qū)崿F(xiàn)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論