Go语言快速排序详解（基准选择策略与性能优化）

基准选择为什么重要？

在 Go实现快排 时，如果总是选择第一个或最后一个元素作为基准，在处理已排序或接近排序的数据时，时间复杂度会退化到 O(n²)，性能急剧下降。

因此，合理的 快速排序基准选择 策略可以显著提升算法在各种输入下的稳定性。常见的策略包括：

• 固定选择：如选首元素、尾元素（简单但易退化）；
• 随机选择：随机选一个元素作基准，平均性能好；
• 三数取中（Median-of-Three）：取首、中、尾三个数的中位数，兼顾简单与性能。

Go语言实现：三数取中基准选择

下面是一个使用“三数取中”策略的完整 Go 快速排序实现：

package mainimport "fmt"// 三数取中：返回首、中、尾三个元素的中位数索引func medianOfThree(arr []int, low, high int) int {    mid := (low + high) / 2    if arr[mid] < arr[low] {        arr[low], arr[mid] = arr[mid], arr[low]    }    if arr[high] < arr[low] {        arr[low], arr[high] = arr[high], arr[low]    }    if arr[high] < arr[mid] {        arr[mid], arr[high] = arr[high], arr[mid]    }    // 此时 arr[mid] 是中位数    return mid}// 分区函数func partition(arr []int, low, high int) int {    // 使用三数取中选择基准    pivotIndex := medianOfThree(arr, low, high)    // 将基准移到末尾    arr[pivotIndex], arr[high] = arr[high], arr[pivotIndex]    pivot := arr[high]    i := low - 1    for j := low; j < high; j++ {        if arr[j] <= pivot {            i++            arr[i], arr[j] = arr[j], arr[i]        }    }    arr[i+1], arr[high] = arr[high], arr[i+1]    return i + 1}// 快速排序主函数func quickSort(arr []int, low, high int) {    if low < high {        pi := partition(arr, low, high)        quickSort(arr, low, pi-1)        quickSort(arr, pi+1, high)    }}// 公共接口func QuickSort(arr []int) {    if len(arr) <= 1 {        return    }    quickSort(arr, 0, len(arr)-1)}// 测试func main() {    data := []int{64, 34, 25, 12, 22, 11, 90}    fmt.Println("排序前:", data)    QuickSort(data)    fmt.Println("排序后:", data)}

性能对比与 算法优化技巧

使用“三数取中”策略后，快排在处理部分有序数据时表现更稳定。相比固定选择首/尾元素，它能有效避免最坏情况的发生。

此外，还可以结合以下 算法优化技巧 进一步提升性能：

• 当子数组长度小于某个阈值（如10）时，改用插入排序；
• 使用尾递归优化减少栈空间消耗；
• 对于大量重复元素，可采用“三路快排”（Dutch National Flag）。

总结

在 Go语言快速排序 中，基准选择绝非小事。通过“三数取中”等策略，我们可以写出既高效又稳定的排序代码。掌握这些 算法优化技巧，不仅能让你的程序跑得更快，还能在面试和实际项目中脱颖而出！

赶快动手试试吧！修改基准选择方式，观察不同数据集下的运行时间，你会对快排有更深的理解。