给定一个包含不同元素的数组，对它进行排序所需的最小交换数量是多少？
例如，阵列[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])
我的方法正确吗？还有另一种解决方法吗？
这取决于您是要查找交换的最小数量还是实际对数组进行排序。
如果您要对数组进行排序，那么最少的交换次数将无法帮助您更快地对其进行排序。寻找最佳的排序算法将帮助您更快地进行排序。通常，这意味着找到复杂度为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之间的差。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句