当前位置：首页 > java >正文

【常用算法：排序篇】3.极速排序秘籍：快排三大优化与高效选择算法

java 2025/5/13 12:26:06

1、高效选择算法

1. 快速选择算法（QuickSelect）

核心思想：基于快速排序的 partition 过程，无需完全排序即可找到第k小（大）元素。
时间复杂度：平均 O(n)，最坏 O(n²)，但通过优化可趋近 O(n)。
应用场景：解决 Top-K 问题（如查找前 K 小元素）。

代码示例：

def quick_select(arr, l, r, k):if l == r:return arr[l]pivot = partition(arr, l, r)if k == pivot:return arr[pivot]elif k < pivot:return quick_select(arr, l, pivot-1, k)else:return quick_select(arr, pivot+1, r, k)

在这里插入图片描述

2. BFPRT算法（中位数的中位数算法）

目标：保证最坏情况下 O(n) 时间复杂度的选择算法。
步骤：
1. 将数组划分为 n/5 组，每组5个元素。
2. 对每组求中位数，形成新的中位数数组。
3. 递归调用BFPRT算法，找到中位数数组的中位数 M。
4. 用 M 作为基准值分区，缩小问题规模。
优势：确定性算法，严格保证 O(n) 时间复杂度。
代码复杂度：实现较复杂，需处理分组和递归逻辑。

2、快速排序三大优化

优化一：单边递归法（减少递归调用）

原理：将左右两边的递归转为循环处理左半边，仅递归处理右半边，减少函数调用开销。
代码示例：

def quick_sort(arr, l, r):while l < r:pivot = partition(arr, l, r)quick_sort(arr, pivot+1, r)  # 递归处理右半边r = pivot - 1                # 循环处理左半边

在这里插入图片描述

优化二：三点取中法（优化基准值选择）

原理：选取头、尾、中间三个元素的中位数作为基准值，避免最坏时间复杂度。
实现逻辑：

def choose_pivot(arr, l, r):mid = (l + r) // 2candidates = sorted([arr[l], arr[mid], arr[r]])return candidates[1]  # 返回中间值

在这里插入图片描述

优化三：双指针 Partition（减少比较次数）

原理：头尾指针同时扫描，交换不满足条件的元素，减少元素比较次数。
代码示例：

def partition(arr, l, r):pivot = choose_pivot(arr, l, r)i, j = l, rwhile i <= j:while arr[i] < pivot: i += 1  # 找左边大于基准的元素while arr[j] > pivot: j -= 1  # 找右边小于基准的元素if i <= j:arr[i], arr[j] = arr[j], arr[i]i += 1j -= 1return i  # 返回分界点

在这里插入图片描述

3、性能对比与选型建议

方法	时间复杂度	优势	适用场景
快速选择算法	O(n)	无需完全排序，高效查找第k元素	Top-K问题、中位数查找
单边递归法	O(nlogn)	减少函数调用，提升运行速度	大规模数据排序
三点取中法	O(nlogn)	避免最坏情况，稳定性高	数据分布不均的场景
双指针Partition	O(nlogn)	减少比较次数，提升局部效率	高频次排序操作