algorithm - 排序排列的最小切换

Question

假设我有一个这样的数组:[5 4 1 2 3]

我想计算对未排序的排列进行排序所需的最小开关。

现在在这种情况下答案是 7。只需将 4 和 5 向右移动，或将 1、2、3 向左移动。

但具有讽刺意味的是，我在笔记中使用了 [4 5 1 2 3]，结果是 6，这误导了我自己，让我自己出丑。

步骤:

[5 1 4 2 3]//步骤 1

[1 5 4 2 3]//步骤 2

[1 5 2 4 3]//步骤 3

[1 2 5 4 3]//第 4 步

[1 2 5 3 4]//步骤 5

[1 2 3 5 4]//第 6 步

[1 2 3 4 5]//第 7 步

我想到了一些事情，比如拥有一个数组来保持所需的偏移量，并且对于每个循环，只需寻找使整个事情更接近目标的开关。

但这似乎太慢了，有什么想法吗？

编辑:来自评论:数组的成员是否保证完全属于 {1..N} 设置为大小为 N 的数组，没有重复数字？

没有。对于大小为 N 的数组，不能保证不重复或不在 [1...n] 中。

更新:

这个特定问题有两种解决方案，一种是速度较慢但更直接的冒泡排序，另一种是速度较快但不太直接的归并排序。

使用冒泡排序，您基本上可以在运行算法时计算开关的数量。

对于合并排序，它有点棘手，但合并时会发生计数。当数组已经合并时，计数应该为 0，因为不需要任何开关来对该数组进行排序。使用冒泡排序，您可以在将最大或最小数字向左或向右推时计算开关数。使用合并排序，您可以在合并时计算开关。我手写暴力破解会让你到达那里。

Answer 1

您实际要查找的是计算序列中的反转次数。

例如，这可以使用合并排序在 O(n*logn) 中完成。

Here你有一篇关于这个主题的文章，看起来很容易理解。

更多链接:

• https://stackoverflow.com/a/338252/2180475
• https://codereview.stackexchange.com/questions/12922/inversion-count-using-merge-sort