查找排序數組的最小交換次數

Question

給定一個具有不同元素的數組，排序所需的最小交換次數是多少？

例如，數組[4, 2, 1, 3]需要至少2次交換（例如交換4和1，然後交換4和3）。

這是我的方法：

B = sort(copy(A)) 
for i = 0 ... len(A) - 1 
    if A[i] != B[i] 
     find j such that A[j] == B[i] 
     swap(A[i], A[j]) 

是我的做法corrert？有其他解決方法嗎？

Answer 1

這取決於您是試圖找到最小交換次數，還是實際嘗試對陣列進行排序。

如果您嘗試對數組進行排序，那麼交換的最小次數不會幫助您更快地排序。找到最好的排序算法將幫助您更快地排序。一般來說，這意味着找到一個具有O（n log（n））複雜性的數據（除非數組很小或者內存是一個主要約束）。爲了解決這個問題，Google是你的朋友。

如果您只是試圖找到所需的最小交換次數，而沒有實際對它進行排序，您正在查看對選擇排序的一些修改。一個人去的方式是找到最低值，與第一個索引交換，找到第二個最低位，與第二個索引交換等。

但正如我所說，找到最小交換量並不會優化排序。例如，選擇排序可能比快速排序的交換次數少，但選擇排序需要更長的時間才能確定要交換的子集。選擇排序的時間複雜度爲O（n^2）。

順便說一句，O（n^2）和O（n log（n））之間的差異並不像看起來那麼平凡。如果這個數字大約是1,000,000，那麼可能是20,000,000和1,000,000,000,000之間的差值。