sorting - 排序后记住元素的 "original"索引

Question

例如，我使用归并排序对整数数组进行排序。现在我还需要记住元素最初在未排序数组中的位置。最好的方法是什么？

一个非常天真的和占用空间的方法是(在 C 中)，将每个数字维护为一个“结构”，另一个数字存储其索引:

struct integer {
int value;
int orig_pos;
};

但是，显然有更好的方法。如果您已经解决了此类问题，请分享您的想法和解决方案。如果您需要更多上下文，请告诉我。谢谢。

Answer 1

很明显，对于一个 N 长的数组，您确实需要在某处存储 N 个整数——例如，每个项目的原始位置；任何其他方式来编码“N 中的 1!”可能性(即实际上发生了什么排列)也将至少占用 O(N) 空间(因为根据斯特林近似，log(N!) 大约是 N log(N)...)。

所以，我不明白为什么您认为最简单直接地存储这些索引是“占用空间”的。当然还有其他可能性(占用类似的空间):例如，您可以制作一个单独的 N 索引辅助数组，然后对该辅助数组进行排序(基于该索引处的值)，而单独保留原始数组。这意味着按排序顺序访问数据的额外级别的间接性，但如果您正在对大型结构数组进行排序，可以为您节省大量数据移动，因此存在性能权衡......但空间消耗基本上是一样!-)