8.4 快速排序

快速排序是一種分而治之的排序算法。它通過隨機選擇一個基準(zhǔn)元素，將數(shù)組分為兩部分。

一部分比基準(zhǔn)元素小，另一部分比基準(zhǔn)元素大，之后對兩部分排序。

快速排序以其平均情況下的 O(n log n) 時間復(fù)雜度和良好的性能而廣泛應(yīng)用。

本節(jié)代碼存放目錄為 lesson20

---

概念與原理

快速排序的基本思想

• 選擇基準(zhǔn)元素：從數(shù)組中選擇一個元素作為基準(zhǔn)，通常選擇第一個元素或最后一個元素，也可以隨機選擇。

• 劃分?jǐn)?shù)組：將數(shù)組中的其他元素與基準(zhǔn)元素進(jìn)行比較，按照小于基準(zhǔn)和大于基準(zhǔn)分成兩部分。

• 遞歸排序：對基準(zhǔn)元素兩側(cè)的子數(shù)組分別遞歸地進(jìn)行快速排序。

• 合并結(jié)果：經(jīng)過每一輪劃分和遞歸，數(shù)組最終變得有序。

總的來說，就是選出一個元素，通過與該基準(zhǔn)元素的對比得到兩個序列，左邊的序列小于基準(zhǔn)，右邊的序列大于基準(zhǔn)。

下一步再分別針對左邊、右邊進(jìn)行遞歸的快速排序，最終左邊、右邊也都是有序的序列。

---

快速排序的步驟示例

給定如下無序數(shù)組，按照從小到大排序：

[5, 3, 8, 4, 2]

通過快速排序的步驟如下：

第一步：選擇基準(zhǔn)元素- 選擇數(shù)組最后一個元素 2 作為基準(zhǔn)，劃分?jǐn)?shù)組。- 比基準(zhǔn)小的元素：[]（沒有元素小于 2）- 比基準(zhǔn)大的元素：[5, 3, 8, 4]- 將基準(zhǔn)元素 2 放在數(shù)組的正確位置，結(jié)果：[2, 3, 8, 4, 5]第二步：遞歸排序- 遞歸排序左側(cè)數(shù)組（空數(shù)組，不需要處理）- 遞歸排序右側(cè)數(shù)組 [3, 8, 4, 5]第三步：選擇基準(zhǔn)元素- 選擇 5 作為基準(zhǔn)，劃分?jǐn)?shù)組。- 比基準(zhǔn)小的元素：[3, 4]
- 比基準(zhǔn)大的元素：[8]- 將基準(zhǔn)元素 5 放在數(shù)組的正確位置，結(jié)果：[2, 3, 4, 5, 8]第四步：遞歸快速排序- 遞歸快速排序左側(cè)數(shù)組 [3, 4]，選擇基準(zhǔn) 4，劃分為 [3] 和 4- 最終排序結(jié)果為 [2, 3, 4, 5, 8]

通過快速排序，數(shù)組最終被排序為 [2, 3, 4, 5, 8]。

---

快速排序的時間復(fù)雜度

快速排序的時間復(fù)雜度取決于基準(zhǔn)元素的選擇：

• 最壞情況：O(n2)，當(dāng)基準(zhǔn)元素總是選擇最小或最大值時，導(dǎo)致數(shù)組無法被均勻劃分。

• 最好情況：O(n log n)，當(dāng)每次劃分都將數(shù)組均勻地分成兩半。

• 平均情況：O(n log n)，通常情況下，快速排序的表現(xiàn)非常接近 O(n log n)。

---

Go語言的實現(xiàn)

實現(xiàn)代碼如下：

// partition 函數(shù)實現(xiàn)數(shù)組的劃分
func partition(arr []int, low, high int) int {pivot := arr[high] // 選擇最后一個元素作為基準(zhǔn)i := low - 1       // i 代表已處理的元素區(qū)間// 遍歷數(shù)組，將小于 pivot 的元素移到前面for j := low; j < high; j++ {if arr[j] < pivot {i++arr[i], arr[j] = arr[j], arr[i]}}// 將基準(zhǔn)元素放到正確位置arr[i+1], arr[high] = arr[high], arr[i+1]return i + 1 // 返回基準(zhǔn)元素的位置
}// quickSort 實現(xiàn)快速排序
func quickSort(arr []int, low, high int) {if low < high {// 劃分?jǐn)?shù)組，并獲取基準(zhǔn)元素的位置pi := partition(arr, low, high)// 遞歸排序基準(zhǔn)左側(cè)和右側(cè)的子數(shù)組quickSort(arr, low, pi-1)quickSort(arr, pi+1, high)}
}func main() {arr := []int{5, 3, 8, 4, 2}quickSort(arr, 0, len(arr)-1)fmt.Println("最終排序結(jié)果: ", arr)
}

執(zhí)行結(jié)果如下所示：

最終排序結(jié)果:  [2 3 4 5 8]

小結(jié)

本節(jié)我們講解了快速排序的基本原理、步驟示例和 Go 語言的實現(xiàn)。

關(guān)于本節(jié)總結(jié)如下：

• 時間復(fù)雜度：快速排序的平均時間復(fù)雜度為 O(n log n)，但最壞情況下會退化為 O(n2)。

• 穩(wěn)定性：快速排序是不穩(wěn)定的排序算法。

• 應(yīng)用場景：快速排序在處理大規(guī)模數(shù)據(jù)時非常高效，適用于數(shù)據(jù)量較大且對排序性能要求高的場景。

---

我的GitHub：https://github.com/swxctx

書籍地址：https://gs.golang.website/

書籍代碼：https://github.com/YouCanGolang/GoStructedCode