1,2,...,n的排列），将其按自然递增顺序（即1,2,...,n）排序。 我考虑直接交换元素（不考虑元素位置；换句话说，对于任意两个元素，交换都是有效的），并用最少的次数进行交换（以下可能是可行的解决方案）：
交换两个元素，并约束其中一个或两个元素应被交换到正确的位置。 直到每个元素都放在正确的位置。
但我不知道如何数学证明上述解决方案是否最优。 有人可以帮忙吗？
我可以用图论来证明这一点。你可能需要添加这个标签 :)
创建一个有n个顶点的图。如果在正确排序中，位置i上的元素应该在位置j上，则从节点n_i 到 n_j创建一条边。现在，你将拥有一个由若干不相交的环组成的图。我认为，正确排序所需的最少交换次数是
M = sum (c in cycles) size(c) - 1
n为奇数，则可能以单个一元循环结束），然后将所有二元循环交换到正确的位置。这也涉及n-1次移动。虽然这不比提供的算法更快，但至少表明提供的算法的最优性显然并不明显。 - Him所有的循环计数都很难记在脑子里，有一种更简单的方法可以记忆。
首先，手动演示一个样例。
swap(0,2);swap(0,3) 和 swap(2,3);swap(0,2) 是相同的。swap(0, 1) => [(3, 2), (1, 1), (2, 3), (4, 4), (5, 5), (6, 6), (0, 7)]swap(0, 3) => [(4, 4), (1, 1), (2, 3), (3, 2), (5, 5), (6, 6), (0, 7)]swap(0, 4) => [(5, 5), (1, 1), (2, 3), (3, 2), (4, 4), (6, 6), (0, 7)]swap(0, 5) => [(6, 6), (1, 1), (2, 3), (3, 2), (4, 4), (5, 5), (0, 7)]swap(0, 6) => [(0, 7), (1, 1), (2, 3), (3, 2), (4, 4), (5, 5), (6, 6)]也就是说，语义上您将元素进行排序，然后通过交换最左侧不在正确位置的项来确定如何将它们放回初始状态。
Python算法就这么简单：
def swap(arr, i, j):
arr[i], arr[j] = arr[j], arr[i]
def minimum_swaps(arr):
annotated = [*enumerate(arr)]
annotated.sort(key = lambda it: it[1])
count = 0
i = 0
while i < len(arr):
if annotated[i][0] == i:
i += 1
continue
swap(annotated, i, annotated[i][0])
count += 1
return count
while (i < enumeratedArr.length) {
if (enumeratedArr[i][1] == i + 1) {
i++
continue
} else {
swap(enumeratedArr, i, enumeratedArr[i][1] - 1)
count++
}
} - Dan Engelstatic int minimumSwaps(int[] arr) {
int swap=0;
boolean visited[]=new boolean[arr.length];
for(int i=0;i<arr.length;i++){
int j=i,cycle=0;
while(!visited[j]){
visited[j]=true;
j=arr[j]-1;
cycle++;
}
if(cycle!=0)
swap+=cycle-1;
}
return swap;
}
j=arr[j]-1;。为什么j的值要减去1，而我们在开始时将其设置为i呢？ - Ashish Santikarij=arr[j]-1;的原因可以通过在已排序的数组上运行代码来看到。在这种情况下，填充visited数组按顺序进行，0是第一个索引，因此需要减去1。在这种情况下，每次while循环后终止1次循环。如果无序，则数组将是暂时稀疏的，循环计数器计算它以正确的顺序“查看”所需的时间，这相当于交换次数，如果您从基于0的索引中减去1。非常酷。 - John Wright供您参考，这是我编写的一个算法，用于生成排序数组所需的最少交换次数。它按照@Andrew Mao描述的方式查找循环。
/**
* Finds the minimum number of swaps to sort given array in increasing order.
* @param ar array of <strong>non-negative distinct</strong> integers.
* input array will be overwritten during the call!
* @return min no of swaps
*/
public int findMinSwapsToSort(int[] ar) {
int n = ar.length;
Map<Integer, Integer> m = new HashMap<>();
for (int i = 0; i < n; i++) {
m.put(ar[i], i);
}
Arrays.sort(ar);
for (int i = 0; i < n; i++) {
ar[i] = m.get(ar[i]);
}
m = null;
int swaps = 0;
for (int i = 0; i < n; i++) {
int val = ar[i];
if (val < 0) continue;
while (val != i) {
int new_val = ar[val];
ar[val] = -1;
val = new_val;
swaps++;
}
ar[i] = -1;
}
return swaps;
}
@Archibald，我喜欢你的解决方案，我最初的假设也是将数组排序是最简单的解决方法，但是我认为没有必要进行所谓的反向遍历，即枚举数组，排序数组然后计算枚举的交换。
我发现将数组中的每个元素减1，然后计算排序所需的交换更简单。
这是我的改进/解决方案：
def swap(arr, i, j):
tmp = arr[i]
arr[i] = arr[j]
arr[j] = tmp
def minimum_swaps(arr):
a = [x - 1 for x in arr]
swaps = 0
i = 0
while i < len(a):
if a[i] == i:
i += 1
continue
swap(a, i, a[i])
swaps += 1
return swaps
关于证明最优性，我认为@arax说得很有道理。
// 假设我们只处理以零开始的序列
function minimumSwaps(arr) {
var len = arr.length
var visitedarr = []
var i, start, j, swap = 0
for (i = 0; i < len; i++) {
if (!visitedarr[i]) {
start = j = i
var cycleNode = 1
while (arr[j] != start) {
j = arr[j]
visitedarr[j] = true
cycleNode++
}
swap += cycleNode - 1
}
}
return swap
}
我非常喜欢@Ieuan Uys在Python中提出的解决方案。
我对他的解决方案进行了改进;
while i < len(a) - 1我的Python代码。
def minimumSwaps(arr):
#make array values starting from zero to match index values.
a = [x - 1 for x in arr]
#initialize number of swaps and iterator.
swaps = 0
i = 0
while i < len(a)-1:
if a[i] == i:
i += 1
continue
#swap.
tmp = a[i] #create temp variable assign it to a[i]
a[i] = a[tmp] #assign value of a[i] with a[tmp]
a[tmp] = tmp #assign value of a[tmp] with tmp (or initial a[i])
#calculate number of swaps.
swaps += 1
return swaps
对长度为n的数组进行编码的详细说明;
我们逐一检查数组中除最后一个值外的每个值（n-1次迭代）。如果该值与数组索引不匹配，则将此值发送到其索引值等于其值的位置。例如，如果在a[0] = 3，则此值应与a[3]交换。a[0]和a[3]被交换。值3将位于其应在的a[3]处。一个值被发送到了它的位置。我们还剩下n-2次迭代。我不关心现在a[0]是什么。如果该位置上不是0，则稍后将通过另一个值进行交换。因为另一个值也存在错误的位置，这将在后面的while循环中被识别。
真实示例
a[4, 2, 1, 0, 3]
#iteration 0, check a[0]. 4 should be located at a[4] where the value is 3. Swap them.
a[3, 2, 1, 0, 4] #we sent 4 to the right location now.
#iteration 1, check a[1]. 2 should be located at a[2] where the value is 1. Swap them.
a[3, 1, 2, 0, 4] #we sent 2 to the right location now.
#iteration 2, check a[2]. 2 is already located at a[2]. Don't do anything, continue.
a[3, 1, 2, 0, 4]
#iteration 3, check a[3]. 0 should be located at a[0] where the value is 3. Swap them.
a[0, 1, 2, 3, 4] #we sent 0 to the right location now.
# There is no need to check final value of array. Since all swaps are done.
Swift 4版本：
func minimumSwaps(arr: [Int]) -> Int {
struct Pair {
let index: Int
let value: Int
}
var positions = arr.enumerated().map { Pair(index: $0, value: $1) }
positions.sort { $0.value < $1.value }
var indexes = positions.map { $0.index }
var swaps = 0
for i in 0 ..< indexes.count {
var val = indexes[i]
if val < 0 {
continue // Already visited.
}
while val != i {
let new_val = indexes[val]
indexes[val] = -1
val = new_val
swaps += 1
}
indexes[i] = -1
}
return swaps
}
ar的初始代码可以简洁地表达为：var origIndexes = Enumerable.Range(0, n).ToArray();
Array.Sort(ar, origIndexes);
然后在代码的其余部分中使用origIndexes而不是ar。
找到将1..N的排列放入顺序所需的最小交换次数。
我们可以利用已知的排序结果：1..N，这意味着我们实际上不必进行交换，只需计算它们。
1..N的洗牌称为排列，并由不相交的循环置换组成，例如，这个1..6的排列：
1 2 3 4 5 6
6 4 2 3 5 1
由循环置换(1,6)(2,4,3)(5)组成
1->6(->1) cycle: 1 swap
2->4->3(->2) cycle: 2 swaps
5(->5) cycle: 0 swaps
因此，一个由k个元素组成的循环需要k-1次交换才能排序。
由于我们知道每个元素“属于”哪个位置（即值k属于位置k-1），因此我们可以轻松地遍历该循环。从0开始，我们得到6，其属于5， 然后我们找到了1，它属于0，我们又回到了起点。
为了避免以后重新计算循环，我们跟踪哪些元素已经访问过—或者你可以执行交换，以便在以后访问时元素会出现在正确的位置。
最终代码：
def minimumSwaps(arr):
visited = [False] * len(arr)
numswaps = 0
for i in range(len(arr)):
if not visited[i]:
visited[i] = True
j = arr[i]-1
while not visited[j]:
numswaps += 1
visited[j] = True
j = arr[j]-1
return numswaps