排序應用程序難度

Question

目前我正在閱讀一本關於算法的書，並發現了這種排序的用法。

重建原始順序 - 在某些應用程序對它們進行排序後，如何恢復一組項目的原始排列？爲項目的數據記錄添加一個額外的字段，以便第i條記錄將該字段設置爲i。每當您移動記錄時都隨身攜帶此字段，並在您希望恢復初始訂單時對其進行排序。

我一直在努力去理解這是什麼意思。我悲慘地失敗了。請有人幫忙？

Answer 1

假設你有按隨機順序的產品清單。

itemC, itemB, itemA, itemD 

你整理起來：

itemA, itemB, itemC, itemD 

，你沒有足夠的內存來存儲它們在一個單獨的位置，所以原始序列丟失。而且，原始順序是隨機的，並且將會有問題/不可能恢復它。

本文提供瞭解決此問題的方法。

一個額外的字段添加到數據記錄的項目，使得i個記錄將此字段設置爲我

所以，我們添加一個額外的領域爲每個項目：

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

我們排序後有：

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

因此，我們可以輕鬆地恢復初始ORD呃按其他字段排序

Answer 2

假設你有一個數組中的數據，因爲它是我可以用來舉例說明的最簡單的結構。

所以，你的節點（即數組的元素）可能是這樣的：

(some data type) data 

的算法建議你添加一個整型字段，所以它看起來是這樣的：

(some data type) data, 
int    position 

然後，您用實際的指數填充位置。事情是這樣的僞代碼：

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

（這不是寫在我所知道的任何語言，但它應該是可讀）

這樣做之後，你將它洗（求助於它）任何你需要。

當你想恢復原來的順序時，你所要做的就是按position字段排序。

Answer 3

嗯，基本上它是說你需要某種東西來跟蹤原始順序（它被排列所破壞）。一種選擇是簡單地改變排列方式（查看史蒂夫傑索普的溫和答案here）。

反轉置換的另一種方法是需要更少的處理步驟，但需要更多的存儲器。更具體地說，輸入集中的每個節點都會有一個額外的ID字段，並且此輸入集中的所有元素都基於此字段進行排序。一旦你應用了排列，顯然這些ID不再是排序順序。如果你想反轉排列，你所要做的就是根據這個字段重新排序列表。