algorithm - 排序申请难度

Question

目前我正在阅读一本关于算法的书，并发现了这种排序的用法。

重建原始顺序 - 我们如何在为某些应用程序排列一组项目后恢复它们的原始排列？为项目的数据记录添加一个额外的字段，以便第 i 条记录将此字段设置为 i。每当您移动记录时，请携带此字段，然后在您想要返回初始订单时对其进行排序。

我一直在努力理解它是什么意思。而我失败得很惨。请有人帮忙吗？

Answer 1

假设您有随机顺序的项目列表：

itemC, itemB, itemA, itemD

你对它们进行了分类：

itemA, itemB, itemC, itemD

而且您没有足够的内存将它们存储在单独的位置，因此原始序列丢失了。此外，原始顺序是随机的，恢复它会有问题/不可能。

这篇文章给出了这个问题的解决方案。

为项目的数据记录添加一个额外的字段，以便第 i 条记录将此字段设置为 i

因此，我们为每个项目添加一个额外的字段：

(itemC,1), (itemB,2), (itemA,3), (itemD, 4)

排序后我们有：

(itemA,3), (itemB,2), (itemC,1), (itemD, 4)

因此我们可以通过附加字段轻松恢复初始订单排序

Answer 2

Let's say you have the data in an array, because it's the simplest structure that I can use to exemplify.

So, your node (i.e., element of the array) may look like this:

 (some data type) data

The algorithm is suggesting you to add an integer field, so it looks like this:

 (some data type) data,
 int              position

And then, you fill the positions with the actual index. Something like this pseudocode:

for current: 0 to lastElement
  array[current].position = current

(that's not written in any language I know of, but it should be readable)

After doing that, you shuffle it (resort it) for whatever you need to.

When you want to restore the original ordering, all you need to do is sort by the position field.

Answer 3

好吧，基本上它是说您需要某种东西来跟踪原始顺序（被排列破坏）。一种选择是简单地反转排列（在此处查看 Steve Jessop 的信息性答案）。

另一种反转排列的选择需要更少的处理步骤，但需要更多的内存。更具体地说，输入集中的每个节点都会有一个额外的 ID 字段，并且此输入集中的所有元素都基于此字段进行排序。应用排列后，很明显 ID 不再按排序顺序。如果您希望反转排列，您所要做的就是根据该字段再次对列表进行排序。