查找最小交换数以对数组进行排序

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])

我的方法正确吗？还有别的办法解决吗？

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 之间的差异。

Find Minimum Number of Swaps to Sort an Array