如何根據另一個數組對數組進行排序？

Question

假設A = {1,2,3,4}，p = {36,3,97,19}，使用p作爲排序關鍵字排序A.您可以獲得{2,4,1,3}。

這是本書介紹算法的一個例子。它說它可以在nlogn中完成。

任何人都可以給我一些關於如何完成的想法嗎？我的想法是，你需要跟蹤p中的每個元素以找到它的最終位置，例如p [1]結束於p [3]，然後A [1]結束於A [3]。任何人都可以使用合併排序或其他nlogn排序來完成這項工作嗎？

我是新來的算法，發現它有點嚇人:(感謝您的幫助

Answer 1

我沒有看到這個困難的，因爲複雜性一個排序算法的通常在所需的比較的數量來測量，你只需要根據在B元素來更新陣列A元件的位置。除了已經需要對B進行排序以外，您不需要進行任何比較，因此複雜性是相同的。

每次移動元素時，只需將它移動到兩個數組中即可完成。

Answer 2

構建索引陣列中。

i = { 0, 1, 2, 3 }

現在，當您正在整理p，使。該指數陣列相同的變化i

當你完成，你必須：

i = { 1, 3, 0, 2 }

對兩個數組排序最多需要排序兩次（實際上，如果只計算比較，則不必進行任何其他比較，只需在兩個數組中進行數據交換） ，因此不會改變整體排序的Big-O複雜性，因爲O(2n log n) = O(n log n)。

現在，您可以使用這些索引在線性時間內構建排序的A數組，只需遍歷排序的索引數組並在該索引處查找A的元素即可。這需要O(n)時間。

整體算法的運行時間複雜性是在最壞的情況：O(n + 2n log n) = O(n log n)

當然，你也可以跳過指數陣列完全和只是簡單地將陣列A以同樣的方式，沿側p排序它。