目錄

前言

快速排序

代碼示例

1. 算法包

2. 快速排序代碼

3. 模擬程序

4. 運行程序

5. 從大到小排序

快速排序的思想

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

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

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

3. 遞歸排序

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

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

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

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

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

快速排序的適用場景

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

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

3. 緩存友好的

---

前言

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

快速排序

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

代碼示例

下面我們使用Go語言實現(xiàn)一個快速排序

1. 算法包

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

touch pkg/algorithm.go

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

2. 快速排序代碼

打開?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)// 分別對基準(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] // 選擇最后一個元素作為基數(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. 模擬程序

打開?main.go?文件，代碼如下：

package mainimport ("demo/pkg""fmt"
)func main() {// 定義一個切片，這里我們模擬 10 個元素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. 運行程序

go run main.go

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

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

5. 從大到小排序

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

修改?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)// 分別對基準(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] // 選擇最后一個元素作為基數(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
}

只需要一丁點的代碼即可

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

快速排序的思想

• 分而治之：將大問題分解為小問題，然后遞歸地解決小問題，最后將小問題的解合并成原問題的解
• 原地排序：快速排序是原地排序算法，它只需要一個很小的?？臻g(用于遞歸)來進(jìn)行排序，不需要額外的存儲空間
• 不穩(wěn)定性：快速排序在某些情況下可能不是穩(wěn)定的排序算法，因為相同元素的相對位置可能會在排序過程中改變

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

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

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

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

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

3. 遞歸排序

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

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

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

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

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

總計循環(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}

總計循環(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}

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

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

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

如果將 120 改成 700

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

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

• 冒泡排序：循環(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?次

快速排序的適用場景

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

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

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

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

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

3. 緩存友好的

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

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

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