咨询从无序数组提取排序后指定索引范围切片的C#高效算法

核心逻辑说明 #

常规全量排序的复杂度为O(n log n)，针对仅需提取排序后[L, R]区间元素的场景，可采用基于快速选择的优化方案，整体平均复杂度可降到O(n + k log k)，其中k = R - L + 1为目标区间长度，当k远小于数组总长度n时，效率远高于全量排序。该方案完全依托快速排序核心的partition逻辑，也就是你提到的“O(n)推导单元素最终有序位置”的特性。

具体实现步骤 #

• 实现快速选择算法时，pivot选择采用三数取中/随机选取策略，避免最坏O(n²)的复杂度
• 第一次调用快速选择，定位排序后左边界索引L对应的元素值，完成partition后，数组中所有小于该值的元素会被划分到索引L左侧，无需关注左侧元素的具体顺序
• 第二次调用快速选择，在数组的[L, n-1]范围内定位排序后右边界索引R对应的元素值，完成partition后，数组中[L, R]区间内的所有元素即为目标元素集合
• 仅对长度为k的目标区间做全量排序，即可得到和全量排序后取切片完全一致的结果

示例验证（对应提问中的用例） #

原无序数组为[2, 3, 1, 9, 5, 4, 7, 3, 3]，目标切片为索引5-7（0开始计数）：

1. 第一次快速选择定位索引L=5的元素，对应排序后的值为4，划分后数组前5位为所有小于等于4的元素[1,2,3,3,3]
2. 第二次快速选择在索引5-8的范围内定位R=7的元素，对应排序后的值为7，划分后索引5-7的元素为[4,5,7]
3. 对这3个元素排序后得到结果4 | 5 | 7，和全量排序后取切片的结果完全一致

C#实现注意点 #

• 可直接原地操作数组，无需额外开辟全量数组的存储空间；如果不希望修改原数组，可先对原数组做一次浅拷贝后再执行划分操作
• 当目标区间长度k接近数组总长度n时，该方案和直接全量排序的效率基本持平，不会产生额外性能损耗
• 如果场景中存在大量重复元素，可采用三向划分的快速选择版本，进一步降低划分阶段的比较次数

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