排序的特殊屬性

Question

有與下列屬性的陣列的陣列：

對於每個X，Y在A，如果x < y，則x的A中的第一次出現是在y中的第一個出現之前A.

如何在avarage上的O（n）中穩定排序數組A.

我正在學習數據結構中的考試，並且在嘗試解決過去的考試時遇到了這個問題。

Answer 1

由於A的屬性，您知道所有元素的第一次出現已經形成了排序列表。其他事件需要在它們各自的第一次發生後以輸入順序（因爲您想要穩定排序）直接結束。

您需要跟蹤列表中的第一次出現。後面的事件需要在從元素到元素列表的散列表中跟蹤。最後，您可以在第一次出現時迭代列表，並在散列表中收集列表。

僞代碼，這將是這樣的：

list: List(Element) 
map: Map(Element -> List(Element)) 

foreach x in A 
    if x exists in map 
     map[x].add(x) 
    else 
     map.[x] = [x] 
     list.add(x) 

result = [] 
foreach x in list 
    result.concat(map[x])