有没有一种排序算法可以最大限度地减少最后值的重用，同时保持有效的时间复杂度？

问：

我正在探索经常重用比较值的排序算法。例如，在快速排序中，枢轴值通常会导致 （23， 5）、（23， 18）、（23， 44） 等比较。我对一种算法感兴趣，该算法可以针对低重用率进行优化，同时保持有效的时间复杂度。

例：

考虑一个比较序列，如 A 与 B、B 与 C、C 与 D、A 与 E。在这里，值 B 从第一次比较到第二次比较被重用，而 C 从第二次比较到第三次被重用。该算法的重用率为 r = .5，因为 2/4 的比较是重用。

问题：

1. 是否有现有的排序算法可以在保持效率的同时本质上最大限度地减少这种最后值的重用？
2. 如果没有，可以建议对标准算法（如快速排序、合并排序等）进行哪些修改来实现这一点？

我测试了一些排序算法的重用率 （r）。冒泡排序、快速排序和插入排序的 r 值都在 .9 左右，这意味着每次比较都与前一个比较共享一个值 ~90% 的时间。壳排序 （r = .4）、梳状排序 （r = .35） 和锦标赛排序 （r = .15） 最低，尽管壳排序在比较数量上优于其他排序。