跳到主要内容

高级排序算法 快速排序

快速排序原理​

快速排序是一种基于分治思想的高效排序算法，由英国计算机科学家托尼·霍尔在1960年提出。它的核心思想是选择一个基准元素（pivot），将数组分割成两个子数组，使得左边子数组的所有元素都小于基准，右边子数组的所有元素都大于基准，然后递归地对两个子数组进行排序。

基本实现：

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 partition(arr []int, low, high int) int {
    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
}

时间复杂度分析​

快速排序的时间复杂度与基准元素的选择密切相关，这直接影响了分区的平衡性。

最优情况 O(n log n)​

当每次分区都能将数组平均分成两半时，递归深度为 log n，每层需要 O(n) 时间进行分区操作。

实际场景：数组元素随机分布，或使用三数取中法选择基准。

最坏情况 O(n²)​

当每次选择的基准都是最小或最大元素时，分区极不平衡，一边为空，另一边有 n-1 个元素。

实际场景：

  • 数组已经排序（正序或逆序）
  • 数组中有大量重复元素
  • 基准选择策略不当
// 最坏情况示例：已排序数组
func worstCase() {
    arr := []int{1, 2, 3, 4, 5, 6, 7, 8} // 每次pivot都是最大值
    // 分区结果：[1,2,3,4,5,6,7] | [] | [8]
    // 递归层数：n-1 层，总复杂度：O(n²)
}

平均情况 O(n log n)​

在随机输入下，快速排序的平均时间复杂度为 O(n log n)，这使得它在实际应用中表现优秀。

空间复杂度分析​

快速排序的空间复杂度主要来自递归调用栈：

  • 最优情况：O(log n) - 递归深度为 log n
  • 最坏情况：O(n) - 递归深度为 n
  • 平均情况：O(log n)

优化策略​

基准选择优化​

三数取中法：选择首、中、尾三个元素的中位数作为基准，避免在已排序数组上的最坏情况。

func medianOfThree(arr []int, low, high int) int {
    mid := (low + high) / 2
    
    // 确保 arr[low] <= arr[mid] <= arr[high]
    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], arr[high] = arr[high], arr[mid]
    return high
}

小数组优化​

当子数组较小时（通常 < 10 个元素），使用插入排序代替快速排序，因为插入排序在小数组上更高效。

func hybridQuickSort(arr []int, low, high int) {
    if high - low < 10 {
        insertionSort(arr, low, high) // 小数组用插入排序
        return
    }
    
    if low < high {
        pi := partition(arr, low, high)
        hybridQuickSort(arr, low, pi-1)
        hybridQuickSort(arr, pi+1, high)
    }
}

三路快排​

对于有大量重复元素的数组，三路快排将数组分成三部分：小于基准、等于基准、大于基准。

实际应用场景：

  • 用户评分系统（大量1-5星重复值）
  • 考试成绩排序（分数集中在某些区间）
  • 库存管理（商品数量有限，重复值多）

实际应用场景​

数据库查询优化​

// 数据库索引排序
type Record struct {
    ID    int
    Score float64
}

func sortDatabaseRecords(records []Record) {
    quickSortRecords(records, 0, len(records)-1)
}

大数据处理​

快速排序特别适合：

  • 外部排序：配合归并排序处理超大文件
  • TopK问题：利用分区特性快速找到第K大元素
  • 并行处理：左右子数组可以并行排序

搜索引擎索引​

搜索引擎需要对网页相关性评分进行排序，快速排序的平均 O(n log n) 性能使其成为理想选择。

与其他排序算法比较​

选择建议：

  • 快速排序：通用场景，对稳定性要求不高
  • 归并排序：需要稳定排序，或最坏情况性能保证
  • 堆排序：内存受限，需要稳定的 O(n log n) 性能
  • 插入排序：小数组（< 50 元素）或部分有序数组

性能优化建议​

编译器优化​

// 避免不必要的边界检查
func optimizedPartition(arr []int, low, high int) int {
    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
}

内存访问优化​

  • 缓存友好：快速排序具有良好的空间局部性
  • 分支预测：现代CPU能较好预测比较分支
  • 并行化：左右子数组可以并行处理
// 并行快速排序示例（简化版）
func parallelQuickSort(arr []int, low, high int, depth int) {
    if depth <= 0 || high - low < 1000 {
        quickSort(arr, low, high) // 串行排序
        return
    }
    
    if low < high {
        pi := partition(arr, low, high)
        
        // 并行处理左右子数组
        go parallelQuickSort(arr, low, pi-1, depth-1)
        parallelQuickSort(arr, pi+1, high, depth-1)
    }
}

快速排序凭借其优秀的平均性能和原地排序的特性，成为了最常用的排序算法之一。通过合理的优化策略，可以在各种实际场景中发挥出色的性能。

Reference​

参考资料 快速排序算法—左右指针法，挖坑法，前后指针法，递归和非递归 参考资料 快速排序算法详解（原理、实现和时间复杂度）