寻求低末值复用率且时间复杂度高效的排序算法及优化方案

研究背景 #

我正在研究存在频繁比较值复用情况的排序算法。例如在快速排序中，基准值常引发(23,5)、(23,18)、(23,44)这类重复复用同一值的比较。核心关注点是：找到或改造出能保持高效时间复杂度，同时最小化比较值复用的算法。

复用率定义示例 #

考虑如下比较序列：A vs B、B vs C、C vs D、A vs E。其中B从第一次比较复用至第二次，C从第二次复用至第三次。该算法的复用率r=0.5，因4次比较中有2次为复用。

核心问题 #

• 是否存在天生能在保持高效性的同时最小化末值复用的现有排序算法？
• 若不存在，可对快速排序、归并排序等标准算法做哪些修改以实现该目标？

已测试算法的复用率数据 #

• 冒泡排序、快速排序、插入排序：r值约为0.9（约90%的比较会与前一次比较共享值）
• 希尔排序：r=0.4，且比较次数表现更优
• 梳排序：r=0.35
• 锦标赛排序：r=0.15

问题解答 #

1. 现有高效低复用率的排序算法 #

从测试数据和算法特性来看：

• 锦标赛排序是天生复用率最低的选项（r=0.15），它的时间复杂度为O(n log n)，属于高效排序范畴，但缺点是需要额外O(n)的辅助空间，空间开销较大。
• 希尔排序是更实用的选择：复用率较低（r=0.4），时间复杂度接近O(n log n)（取决于增量序列的设计），且空间复杂度为O(1)，不需要额外辅助空间。
• 若场景允许使用非比较类排序，基数排序完全不存在比较值复用的问题，它的时间复杂度为O(d(n+k))（d为位数，k为基数），效率很高，但仅适用于整数、固定长度字符串等特定类型的数据。

2. 对标准排序算法的修改方案 #

针对快速排序的修改

• 多基准值划分：放弃单一基准，改用三基准甚至多基准策略。比如三基准快速排序，会选择三个基准值将数组划分为四个区间，每次比较时轮换使用不同基准，避免反复复用同一基准值，直接降低复用率。
• 动态基准切换规则：在递归处理子数组时，强制要求当前基准与上一层递归的基准值不同；或者设置阈值，当同一基准连续复用超过N次时，重新选择新基准，打破复用循环。
• 批量比较优化：分区时先收集一批待比较元素，再统一与基准值比较，而不是逐个连续比较，减少相邻比较的复用概率。

针对归并排序的修改

• 调整归并顺序：传统归并排序优先归并相邻子数组，导致频繁复用子数组的边界值。可以改为优先归并不相邻的子数组，比如间隔一个子数组进行归并，减少连续比较中对同一边界值的复用。
• 多路归并替代二路归并：将传统的二路归并改为k路归并（如4路、8路），每次比较时从k个不同子数组的当前指针值中选择极值，相邻比较的候选值轮换更频繁，大幅降低单个值的复用率。
• 批量归并优化：在归并阶段，批量读取两个子数组的一段元素，先对这段元素进行局部排序后再合并，减少逐元素比较时的复用情况。

内容的提问来源于stack exchange，提问作者thatchedroof