2012-04-24 148 views
1

假設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排序來完成這項工作嗎?

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

回答

1

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

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

+0

阿哈,當再次想到時,它真的不難〜 – Gnijuohz 2012-04-24 02:33:36

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排序它。

相關問題