高效排序算法之快排

快速排序（快排）是一种基于分治思想的高效排序算法，通过递归地将数组划分为较小和较大的子数组实现排序，平均时间复杂度为 O(nlogn)，适用于大规模数据排序。

1. 什么是快速排序

快速排序是对基本排序算法的升级，广泛应用于计算机科学领域（如 Pascal、C++ 等语言）。
它通过多次比较和交换实现排序，是高频算法题中必须掌握的经典排序方法。

2. 核心思想

分治策略：通过选择一个“分界值”（pivot），将数组分为两部分：
左边部分的所有元素小于分界值。
右边部分的所有元素大于或等于分界值。
递归排序：对分界值左右两侧的子数组重复上述过程，直到子数组长度为 1 或 0（即已有序）。
关键步骤：
选择分界值（通常为数组首元素）。
遍历数组，将小于分界值的元素移到左侧，大于或等于的移到右侧。
固定分界值的位置，递归处理左右子数组。

分界值的作用：每趟排序后，分界值的位置固定，且其左侧元素均小于它，右侧元素均大于或等于它。
递归终止条件：当子数组长度为 1 或 0 时，排序完成。

3. 代码实现（Go 语言）

核心函数：
QuickSort：递归调用，处理左右子数组。
partition：一趟排序，确定分界值位置并划分数组。

func QuickSort(a []nums, left, right int) { if left >= right { return } key := partition(a, left, right) // 获取分界值下标 QuickSort(a, left, key-1) // 递归排序左子数组 QuickSort(a, key+1, right) // 递归排序右子数组}func partition(a []nums, left, right int) int { key, idx := nums[left], left+1 // 分界值为首元素，idx为下一个待比较位置 for j := left + 1; j <= right; j++ { if nums[j] < key { a[idx], a[j] = a[j], a[idx] // 交换元素 idx++ } } a[idx-1], a[left] = a[left], a[idx-1] // 分界值归位 return idx - 1}

代码逻辑：
QuickSort 检查递归终止条件（left >= right）。
partition 选择分界值（nums[left]），并通过遍历数组完成划分。
交换元素确保左侧小于分界值，右侧大于或等于分界值。
返回分界值下标，供递归调用使用。

4. 性能分析

时间复杂度：
理想情况：每次划分将数组平分，递归深度为 logn，每趟排序时间为 O(n)，总时间为 O(nlogn)。
最坏情况：每次划分选到最小或最大元素（如数组已有序），递归深度为 n，总时间为 O(n2)。
平均情况：通过随机化分界值或“三者取中”策略，可避免最坏情况，保持 O(nlogn)。
空间复杂度：
递归调用栈的空间消耗为 O(logn)（理想情况）或 O(n)（最坏情况）。
优化策略：
三者取中：从 nums[left]、nums[right] 和 nums[(left+right)/2] 中选中间值作为分界值。
随机化分界值：随机选择一个元素作为分界值，降低最坏情况概率。
稳定性：快速排序是不稳定的排序算法（相同元素的相对位置可能改变）。
适用场景：
大规模数据排序（如内存中的数组）。
对平均性能要求较高，且可接受最坏情况风险的场景。

总结：快速排序通过分治思想和递归实现高效排序，平均时间复杂度为 O(nlogn)，但需注意最坏情况的优化。其简洁性和高效性使其成为内部排序的首选方法之一。

您可能感兴趣问答

Collapsible

热门标签

热点问答