排序应用程序难度

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)

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