排序算法是数据结构与算法中的核心内容，而**快速排序（Quick Sort）**则是其中效率非常高的一种。它在平均情况下的时间复杂度为 O(n log n)，并且采用分治法实现，非常适合递归思想教学与工程实践。
一、快速排序简介
快速排序通过以下步骤实现：
- 1. 从数组中选取一个基准元素（pivot）
- 2. 将比它小的元素放左边，比它大的放右边（分区 partition）
- 3. 对左子数组和右子数组递归排序
特点：
- • 时间复杂度：
- • 最优：O(n log n)
- • 最坏：O(n²)（极端不均匀划分时）
- • 空间复杂度：O(log n)（递归调用栈）
- • 排序方式：原地排序、非稳定排序
二、Go语言实现快速排序（整数切片）
我们先实现一个基础版：排序 []int 切片。
1. 快速排序函数
package sortalgo func QuickSort(arr []int) { if len(arr) < 2 { return } quickSort(arr, 0, len(arr)-1) }
2. 递归核心逻辑
func quickSort(arr []int, left, right int) { if left >= right { return } pivotIndex := partition(arr, left, right) quickSort(arr, left, pivotIndex-1) quickSort(arr, pivotIndex+1, right) }
3. 分区函数（Lomuto 分区法）
func partition(arr []int, left, right int) int { pivot := arr[right] // 选取最后一个元素作为 pivot i := left - 1 // i 代表小于 pivot 的边界 for j := left; j < right; j++ { if arr[j] <= pivot { i++ arr[i], arr[j] = arr[j], arr[i] } } arr[i+1], arr[right] = arr[right], arr[i+1] // 把 pivot 放到正确位置 return i + 1 }
三、使用示例
package main import ( "fmt" "sortalgo" ) func main() { arr := []int{9, 2, 5, 3, 7, 1, 8} fmt.Println("原始数组：", arr) sortalgo.QuickSort(arr) fmt.Println("排序后：", arr) }
输出：
原始数组： [9 2 5 3 7 1 8] 排序后： [1 2 3 5 7 8 9]
四、进阶扩展
✅ 泛型版本（Go 1.18+）
如果你想让快速排序支持任意类型，比如 []float64 或 []string，可以用泛型 + 比较函数：
func QuickSortGeneric[T any](arr []T, less func(a, b T) bool) { var qsort func(left, right int) qsort = func(left, right int) { if left >= right { return } pivot := arr[right] i := left - 1 for j := left; j < right; j++ { if less(arr[j], pivot) { i++ arr[i], arr[j] = arr[j], arr[i] } } arr[i+1], arr[right] = arr[right], arr[i+1] pivotIndex := i + 1 qsort(left, pivotIndex-1) qsort(pivotIndex+1, right) } if len(arr) > 1 { qsort(0, len(arr)-1) } }
调用示例：
QuickSortGeneric([]string{"pear", "apple", "banana"}, func(a, b string) bool { return a < b })
五、总结
通过本篇实战，你已经掌握了：
- • 快速排序的核心原理：选 pivot、分区、递归排序
- • 如何用 Go 语言实现快速排序
- • 如何扩展成泛型排序函数，适用于不同类型数据
快速排序是许多语言标准库（包括 Go sort 包）中核心排序算法的底层实现之一，掌握它对理解排序机制和编写高效代码至关重要。
