查找交换的最小数量以对数组进行排序 [英] Find Minimum Number of Swaps to Sort an Array

问题描述

给出一个包含不同元素的数组，对它进行排序所需的最少交换次数是多少?

Given an array with distinct elements, what is the minimum number of swap needed to sort it?

例如，数组[4, 2, 1, 3]至少需要进行两次交换(例如交换4和1，然后交换4和3).

For example, the array [4, 2, 1, 3] needs at least 2 swaps (e.g. swapping 4 and 1 then 4 and 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])

我的方法正确吗?还有另一种解决方法吗?

Is my approach corrert? Is there another way to solve it?

推荐答案

这取决于您是要查找交换的最小数量还是实际对数组进行排序.

That depends on whether you're trying to find the minimum number of swaps, or actually trying to sort the array.

如果您要对数组进行排序，那么最少的交换次数将无法帮助您更快地对其进行排序.寻找最佳的排序算法将帮助您更快地进行排序.通常，这意味着找到复杂度为O(n log(n))的对象(除非数组很小或内存是主要约束).要获得有关此问题的帮助，Google是您的朋友.

If you're trying to sort the array, the minimum number of swaps will not help you sort it faster. Finding the best sorting algorithm will help you sort faster. Generally, that means finding one with an O(n log(n)) complexity (unless the array is small or memory is a major constraint). For help with this problem, Google is your friend.

如果您只是试图查找所需的最小交换次数，而没有对其进行实际排序，那么您正在考虑对选择排序进行一些修改.一个人走的路是找到最小值，与第一个索引交换，找到第二个最低，与第二个索引交换，等等.

If you're just trying to find the minimum number of swaps needed, without actually sorting it, you're looking at some modification of the selection sort. The way that one goes is find the lowest value, swap with the first index, find the second-lowest, swap with the second index, etc.

但是，正如我所说，找到最小的交换数量并不能优化排序.例如，选择排序的交换可能比快速排序的交换要少，但是选择排序确定要交换哪些索引的时间会更长.选择排序的时间复杂度为O(n ^ 2).

But as I said, finding the minimum amount of swaps does not optimize sorting. The selection sort may have fewer swaps than the quicksort, for example, but it takes longer for the selection sort to determine which indeces to swap. The time complexity of the selection sort is O(n^2).

顺便说一句，O(n ^ 2)和O(n log(n))之间的区别并不像看起来那么琐碎.如果数字大约为1,000,000，则可能是20,000,000与1,000,000,000,000之间的差.

The difference between O(n^2) and O(n log(n)) is not as trivial as it looks, by the way. If the number is around 1,000,000, it could be the difference between 20,000,000 and 1,000,000,000,000.

这篇关于查找交换的最小数量以对数组进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！