>假设我们有一个 Mystery-Sort(A)，它接受数组 A 长度 n 作为输入，按非降序对 A 中的数字进行排序，并返回排序后的数组。
我们不知道Mystery-Sort实现的算法是否稳定。 我需要一个过程，它接受一个由 n 个整数组成的数组并以非降序返回排序的数组，但我需要该过程是稳定的。
我怎样才能实现稳定排序过程 Stable-Sort(A) 的伪代码，它预处理和/或后处理 A中的元素在O(n)时间内，只对神秘排序进行一次调用，并返回 按非降序排序的数组。
我认为这分为两个阶段：预处理阶段，您可以在其中找到所有重复的元素及其标识符;在后处理阶段，您只需将找到的元素覆盖到其原始顺序中即可。
您没有指定如何区分排序为相同值的元素;我称之为id. 在第一次传递中，构造一个表，每个值一行。 遍历数组;将每个元素(或整个元素)的 ID 存储在表中的匹配表行中。 如果那里已经有一个元素，请扩展该行并存储当前元素。
此时，如果您愿意，可以删除表中少于 2 个元素的任何行。
对于后处理，循环访问排序后的数组。 如果您找到的值在表中，则不要信任从神秘排序返回的顺序。 相反，只需用表的该行中的元素覆盖下一个元素。 这将恢复其原始顺序。
当您到达排序列表的末尾时，您就完成了。