如何用O(n)额外内存实现任意n元素数组排序算法的稳定化？

堆排序的稳定实现 #

堆排序原生不稳定的核心原因是堆调整过程中，相同值元素的相对位置会被打乱。用O(n)额外内存可通过以下方式实现稳定：

• 遍历原数组，为每个元素附加原始索引，形成(元素值, 原始索引)的结构。排序比较时，优先比较元素值；值相等则比较原始索引，以此保证相同值元素的原始顺序不变。
• 基于带索引的元素结构构建最大堆（升序排序场景），堆调整、元素取出的逻辑均遵循上述比较规则。
• 最后从排序后的结构中提取原始元素值即可，整个过程的额外内存开销为O(n)。

快速排序的稳定实现 #

快速排序的稳定性取决于分区逻辑，用O(n)内存可避免交换操作打乱相同元素的相对位置：

• 同样为每个元素附加原始索引，比较规则与堆排序一致：先比元素值，值相等则按原始索引判断顺序。
• 分区阶段不直接在原数组内交换元素，而是使用两个临时数组：一个存储小于基准值的元素，另一个存储大于等于基准值的元素（等于基准值的元素需保留原始顺序）。
• 递归处理两个临时数组，最终将左数组+基准元素+右数组拼接，替换原数组对应分区。该实现的额外内存开销为O(n)，平均时间复杂度仍保持O(nlogn)。

核心要点 #

• 附加原始索引是实现两种排序稳定性的关键，通过原始索引锚定相同值元素的初始相对顺序。
• 两种实现均未改变原排序算法的时间复杂度，仅通过O(n)额外内存完成稳定性改造。

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