如何预生成排序a、b比较对列表并基于比较结果完成列表稳定排序
2026-10-2
可行实现方案
你需要选择非自适应稳定排序算法即可满足需求，这类算法的比较顺序完全固定，和输入元素值、比较函数逻辑无关，你可以提前一次性生成所有需要的比较对，不需要动态调整比较流程。
核心实现步骤
1. 预生成固定的a、b比较对列表
推荐直接使用奇偶转置排序（Odd-Even Transposition Sort），这是原生稳定的非自适应排序算法，长度为n的列表只需要固定n轮比较，每轮的比较对完全固定：
- 奇数轮：比较所有索引为
(i, i+1)的元素对，i从0开始取偶数（0、2、4...） - 偶数轮：比较所有索引为
(i, i+1)的元素对，i从1开始取奇数（1、3、5...）
你可以按上述规则提前把所有比较对的索引存下来，再对应取出原列表的元素拼成a、b列表即可，不需要考虑原列表的元素顺序和比较函数逻辑。
小技巧：预生成比较对时优先存元素索引而非元素值，可以完全避免元素值重复时无法区分的问题，也不需要限制before、after的取值范围。
2. 生成before、after结果列表
按顺序执行每一组比较对的比较逻辑：
- 若a[i]需要排在b[i]前面：
before[i]填非null值，after[i]填null - 若b[i]需要排在a[i]前面：
before[i]填null，after[i]填非null值 - 若两者相等不需要调整顺序：
before[i]和after[i]同时填非null值或同时填null，符合你要求的保留原始相对顺序的规则。
3. 执行最终排序
按照你生成比较对的顺序逐组处理结果：
- 若
before[i]非null、after[i]为null：不交换两个元素的位置 - 若
before[i]为null、after[i]非null：交换两个元素的位置 - 若两者同时为null或同时非null：不交换，保留原始相对顺序
所有比较对处理完成后，得到的就是稳定排序后的结果。
示例验证
以你提到的[2, 3, 1]降序排序为例，列表长度n=3，预生成的比较对索引序列为：
a索引 = [0, 1, 0] b索引 = [1, 2, 1]
对应a、b元素列表为：
a = [2, 3, 3] b = [3, 1, 2]
比较结果before = [null, 3, 3]，after = [3, null, null]，逐组处理后最终得到排序结果[3, 2, 1]，符合预期。
内容的提问来源于stack exchange，提问作者Kevin Beal
相关产品推荐
相关产品推荐
