目錄

前言

快速排序

代碼示例

1. 算法包

2. 快速排序代碼

3. 模擬程序

4. 運(yùn)行程序

5. 從大到小排序

快速排序的思想

快速排序的實(shí)現(xiàn)邏輯

1. 選擇基準(zhǔn)值 (Pivot)

2. 分區(qū)操作 (Partition)

3. 遞歸排序

循環(huán)次數(shù)測(cè)試

假如?10 條數(shù)據(jù)進(jìn)行排序

假如?20 條數(shù)據(jù)進(jìn)行排序

假如?30 條數(shù)據(jù)進(jìn)行排序

假設(shè) 5000 條數(shù)據(jù)，對(duì)比 冒泡、選擇、插入、堆、歸并

快速排序的適用場(chǎng)景

1. 大數(shù)據(jù)集

2. 隨機(jī)數(shù)據(jù)

3. 緩存友好的

---

前言

在實(shí)際場(chǎng)景中，選擇合適的排序算法對(duì)于提高程序的效率和性能至關(guān)重要，本節(jié)課主要講解"快速排序"的適用場(chǎng)景及代碼實(shí)現(xiàn)。

快速排序

快速排序(Quick Sort) 是一種非常高效的排序算法，采用分治法的策略來(lái)把一個(gè)序列分為較小和較大的兩個(gè)子序列，然后遞歸地排序兩個(gè)子序列。其基本思想是：選擇一個(gè)基準(zhǔn)值(pivot)，通過(guò)一趟排序?qū)⒋判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另一部分的所有數(shù)據(jù)要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以達(dá)到整個(gè)數(shù)據(jù)變成有序序列。

代碼示例

下面我們使用Go語(yǔ)言實(shí)現(xiàn)一個(gè)快速排序

1. 算法包

創(chuàng)建一個(gè)?pkg/algorithm.go

touch pkg/algorithm.go

(如果看過(guò)上節(jié)課的插入排序，則已存在該文件，我們就不需要再創(chuàng)建了)

2. 快速排序代碼

打開(kāi)?pkg/algorithm.go?文件，代碼如下

從小到大?排序

package pkg// BubbleSort 冒泡排序
...// SelectionSort 選擇排序
...// InsertionSort 插入排序
...// QuickSort 快速排序
func QuickSort(arr []int, low, high int) {if low < high {// partitionIndex 是分區(qū)操作后基準(zhǔn)的索引partitionIndex := partition(arr, low, high)// 分別對(duì)基準(zhǔn)左側(cè)和右側(cè)的子數(shù)組進(jìn)行快速排序QuickSort(arr, low, partitionIndex-1)QuickSort(arr, partitionIndex+1, high)}
}// partition 分區(qū)操作
func partition(arr []int, low, high int) int {pivot := arr[high] // 選擇最后一個(gè)元素作為基數(shù)i := low - 1for j := low; j < high; j++ {// 如果當(dāng)前元素小于或等于基數(shù)if arr[j] <= pivot {i++// 交換 arr[i] 和 arr[j]arr[i], arr[j] = arr[j], arr[i]}}// 交換 arr[i+1] 和 arr[high] (基準(zhǔn)值)arr[i+1], arr[high] = arr[high], arr[i+1]return i + 1
}

3. 模擬程序

打開(kāi)?main.go?文件，代碼如下：

package mainimport ("demo/pkg""fmt"
)func main() {// 定義一個(gè)切片，這里我們模擬 10 個(gè)元素arr := []int{51, 224, 67, 322, 825, 103, 50, 965, 789, 601}fmt.Println("Original data:", arr) // 先打印原始數(shù)據(jù)pkg.QuickSort(arr, 0, len(arr)-1)  // 調(diào)用快速排序fmt.Println("New data:  ", arr)    // 后打印排序后的數(shù)據(jù)
}

4. 運(yùn)行程序

go run main.go

能發(fā)現(xiàn)，?Original data?后打印的數(shù)據(jù)，正是我們代碼中定義的切片數(shù)據(jù)，順序也是一致的。

New Data?后打印的數(shù)據(jù)，則是經(jīng)過(guò)快速排序后的數(shù)據(jù)，是從小到大的。

5. 從大到小排序

如果需要?從大到小?排序也是可以的，在代碼里，將兩個(gè)元素比較的?小于等于符號(hào)?改成?大于等于符號(hào)?即可。

修改?pkg/algorithm.go?文件：

package pkg// BubbleSort 冒泡排序
...// SelectionSort 選擇排序
...// InsertionSort 插入排序
...// QuickSort 快速排序
func QuickSort(arr []int, low, high int) {if low < high {// partitionIndex 是分區(qū)操作后基準(zhǔn)的索引partitionIndex := partition(arr, low, high)// 分別對(duì)基準(zhǔn)左側(cè)和右側(cè)的子數(shù)組進(jìn)行快速排序QuickSort(arr, low, partitionIndex-1)QuickSort(arr, partitionIndex+1, high)}
}// partition 分區(qū)操作
func partition(arr []int, low, high int) int {pivot := arr[high] // 選擇最后一個(gè)元素作為基數(shù)i := low - 1for j := low; j < high; j++ {// 如果當(dāng)前元素大于或等于基數(shù)if arr[j] >= pivot {i++// 交換 arr[i] 和 arr[j]arr[i], arr[j] = arr[j], arr[i]}}// 交換 arr[i+1] 和 arr[high] (基準(zhǔn)值)arr[i+1], arr[high] = arr[high], arr[i+1]return i + 1
}

只需要一丁點(diǎn)的代碼即可

從?package pkg?算第一行，上面示例中在第三十一行代碼中，我們將?"<="?改成了?">="?，這樣就變成了 從大到小排序了

快速排序的思想

• 分而治之：將大問(wèn)題分解為小問(wèn)題，然后遞歸地解決小問(wèn)題，最后將小問(wèn)題的解合并成原問(wèn)題的解
• 原地排序：快速排序是原地排序算法，它只需要一個(gè)很小的?？臻g(用于遞歸)來(lái)進(jìn)行排序，不需要額外的存儲(chǔ)空間
• 不穩(wěn)定性：快速排序在某些情況下可能不是穩(wěn)定的排序算法，因?yàn)橄嗤氐南鄬?duì)位置可能會(huì)在排序過(guò)程中改變

快速排序的實(shí)現(xiàn)邏輯

1. 選擇基準(zhǔn)值 (Pivot)

• 在快速排序中，首先需要選擇一個(gè)基準(zhǔn)值(pivot)?；鶞?zhǔn)值的選擇對(duì)排序的效率有很大的影響，但在本文的示例代碼中，我們簡(jiǎn)單地選擇了數(shù)組的最后一個(gè)元素作為基準(zhǔn)值

2. 分區(qū)操作 (Partition)

• 分區(qū)操作是快速排序的核心。它的目的是將數(shù)組重新排列，使得所有比基準(zhǔn)值小的元素都移到基準(zhǔn)值的左邊，所有比基準(zhǔn)值大的元素都移到右邊。分區(qū)操作完成后，基準(zhǔn)值就處于其最終排序位置
• 在 partition 函數(shù)中，我們使用兩個(gè)指針 i 和 j，其中 i 指向小于基準(zhǔn)值的最后一個(gè)元素的下一個(gè)位置(初始化為 low - 1)， j 用于遍歷數(shù)組 (從 low 開(kāi)始到 high - 1)。當(dāng) arr[j] 小于或等于基準(zhǔn)值時(shí)，我們將其與 arr[i+1] 交換，并將 i 增加 1。這樣，所有小于或等于基準(zhǔn)值的元素都被交換到了基準(zhǔn)值的左邊
• 最后，我們將基準(zhǔn)值 (原本在 arr[high] ) 與 arr[i + 1] 交換，此時(shí) i + 1 就是基準(zhǔn)值的最終位置，也是分區(qū)操作的返回值

3. 遞歸排序

• 分區(qū)操作完成后，我們得到了基準(zhǔn)值的正確位置，并且數(shù)組被分成了兩部分：一部分是基準(zhǔn)值左邊的所有元素 (都比基準(zhǔn)值小)，另一部分是基準(zhǔn)值右邊的所有元素 (都比基準(zhǔn)值大)
• 然后，我們遞歸地對(duì)這兩部分分別進(jìn)行快速排序。這是通過(guò)調(diào)用 QuickSort 函數(shù)，并傳入適當(dāng)?shù)膮?shù) (基準(zhǔn)值左側(cè)和右側(cè)的子數(shù)組的范圍) 來(lái)實(shí)現(xiàn)的

循環(huán)次數(shù)測(cè)試

按照上面示例進(jìn)行測(cè)試

假如?10 條數(shù)據(jù)進(jìn)行排序

[]int{51, 224, 67, 322, 825, 103, 50, 965, 789, 601}

總計(jì)循環(huán)了 30 次

假如?20 條數(shù)據(jù)進(jìn)行排序

[]int{997, 387, 461, 530, 979, 502, 36, 459, 99, 60, 454, 37, 182, 273, 529, 130, 315, 351, 975, 497}

總計(jì)循環(huán)了 83?次

假如?30 條數(shù)據(jù)進(jìn)行排序

[]int{755, 247, 642, 652, 38, 587, 387, 284, 476, 924, 339, 830, 614, 534, 832, 450, 8, 641, 768, 788, 472, 750, 169, 479, 386, 124, 868, 259, 550, 613}

總計(jì)循環(huán)了 138?次

上面我們說(shuō)到，"基準(zhǔn)值的選擇對(duì)排序的效率有很大的影響"，我們修改一條，依舊使用 30 條數(shù)據(jù)，我們將其最后一位數(shù)據(jù) 613，改成其他數(shù) 120 (這個(gè)值可隨便改，這里示例 120)

通過(guò)調(diào)試，循環(huán)了 151 次

如果將 120 改成 700

通過(guò)調(diào)試，循環(huán)了 131 次

假設(shè) 5000 條數(shù)據(jù)，對(duì)比 冒泡、選擇、插入、堆、歸并

• 冒泡排序：循環(huán)次數(shù)?12,502,499?次
• 選擇排序：循環(huán)次數(shù)?12,502,499?次
• 插入排序：循環(huán)次數(shù)?6,323,958?次
• 快速排序：循環(huán)次數(shù)?74,236?次
• 堆排序：循環(huán)次數(shù)?59,589?次
• 歸并排序：循環(huán)次數(shù)?60,288?次

快速排序的適用場(chǎng)景

快速排序在多種情況下都是非常高效的，特別是以下幾種情況：

1. 大數(shù)據(jù)集

對(duì)于大數(shù)據(jù)集，快速排序通常比簡(jiǎn)單的排序算法 (如 冒泡排序、插入排序) 更快

2. 隨機(jī)數(shù)據(jù)

當(dāng)輸入數(shù)組中的數(shù)據(jù)是隨機(jī)分布的時(shí)，快速排序的平均時(shí)間復(fù)雜度是 O(n log n)，這是非常高效的

3. 緩存友好的

快速排序通過(guò)遞歸地在數(shù)組的不同部分上工作，傾向于產(chǎn)生良好的緩存局部性，特別是在處理大數(shù)據(jù)集時(shí)

然后，快速排序在某些情況下可能不是最佳選擇，例如：

• 小數(shù)據(jù)集：對(duì)于非常小的數(shù)據(jù)集，快速排序的遞歸開(kāi)銷(xiāo)可能使得它不如簡(jiǎn)單的排序算法 (如 插入排序) 快
• 幾乎已經(jīng)排序的數(shù)據(jù)：在這種情況下，快速排序的性能可能退化為 O(n^2)，因?yàn)樗蕾?lài)于分區(qū)操作來(lái)減少問(wèn)題的規(guī)模。如果分區(qū)操作不能有效地減少數(shù)組的大小 (例如，基準(zhǔn)值總是最大或最小的元素)，則會(huì)導(dǎo)致性能下降。在這種情況下，可以考慮使用歸并排序或堆排序等算法
• 不穩(wěn)定的排序需求：雖然快速排序在大多數(shù)情況下是穩(wěn)定的 (如果實(shí)現(xiàn)得當(dāng))，但在某些特定實(shí)現(xiàn)中可能不是。如果穩(wěn)定性是排序算法的一個(gè)關(guān)鍵要求，可能需要考慮其他算法