確定一個數字列表的順序（可能沒有排序）

Question

我有一個獨特的整數數組（例如val[i]），以任意順序，我想填充另一個數組（ord[i]）的排序索引的整數。換句話說，val[ord[i]]是有序增加i。

現在，我只是用0，...，N填充ord，然後根據值數組對它進行排序，但我想知道是否我們可以更高效地處理它，因爲ord未填充爲開頭。這更多的是出於好奇的問題;我並不在乎需要預先填充列表，然後對它進行排序（這很小，我使用插入排序）。這可能是一個愚蠢的問題，有一個明顯的答案，但我在網上找不到任何東西。

Answer 1

在時間複雜度方面，有不能大於排序更快的方法。如果有的話，那麼你可以使用它來更快地排序：生成索引，然後使用它們重新排序原始數組以排序。這種重新排序會花費線性時間，所以總體而言，您將有一個更快的排序算法，產生矛盾。

Answer 2

插入排序是IIRC相當低C這樣的作品確定小名單（其也不錯，幾乎排序的列表），但是你確定你的列表是足夠小，具有更好的最壞情況下的複雜性排序不會是更好嗎？非就地合併或快速排序似乎符合該法案很好（快速排序可能移交給另一種類非常小的列表反正作爲優化）。

最終知道哪個更快，你將不得不輪廓，大O字只告訴你如何複雜成長，如N - >無限