2

假设我有一个这样的数组： [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

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

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

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

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

更新：

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

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

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

4

2 回答 2

3

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

例如，这可以通过O(n*logn)使用归并排序来完成。

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

更多链接：

于 2013-09-04T09:26:53.423 回答
2

这看起来与冒泡排序非常相似，其中您最多需要 n^2 次移动。

有趣的事实是，简单的冒泡排序实际上实现了您的目标，即找到最少开关数！（证明如下）

在这种情况下，我们不需要使用双循环进一步改进算法，实际上可以使用双循环（在 C++ 中）：

int switch = 0;
for(int repeat=0; repeat<n; repeat++){
    for(int j=0; j<n-repeat; j++){
        if(arr[j]>arr[j+1]){
            int tmp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = tmp;
            switch = switch + 1
        }
    }
}

结果switch就是。
arr是包含数字的数组。
n是数组的长度。

证明这会产生最小数量的开关：

首先，我们注意到冒泡排序本质上是在每次迭代（外循环）时将最高元素移动到数组中最右边的位置

请注意，在过程中将最高元素与任何其他元素进行切换不会改变其他元素的相对顺序。而且在我们尝试将最高元素移动到其位置之间所做的任何其他开关操作都不会改变将最高元素移动到位置所需的开关数量。所以我们可以互换开关操作，这样最高的元素总是首先被切换，直到它就位。因此，一次将最高元素切换到其位置是最佳的。

于 2013-09-04T01:46:03.277 回答