algorithm - 尽可能排序 : values can travel no more than k positions to their left

Question

Given an array of length N and an integer K, sort the array as much as possible such that no element travels more than K positions to its left. An element however can travel as much as it likes to its right.

Let's define sortedness as the number of disordered pairs, i.e.: sortedness(1,2,3) = 0 and sortedness(3,1,2) = 2.

Clarification: If the first k+1 items of the array are moved to the end of the array, the other ones should be considered moved k+1 positions to the left.

这是一道面试题。我想到了使用冒泡排序。外循环将运行 K 次，运行时间为 O(nk)。最小的整数将是唯一向左移动 K 次的整数。其他整数将向左移动少于 K 次。

有没有更有效的方法来解决这个问题？

Answer 1

使用最小堆对包含 n 个元素的列表进行排序，复杂度为 O(n log k)。

1. 将前 k+1 个未排序的元素添加到堆中。
2. 重复此步骤:从堆中弹出最小元素。将其添加到排序列表的末尾。将下一个未排序的元素添加到堆中。

因为无论n个多少，堆总是最多有k+1个元素，所有堆操作都是O(log k)，总运行时间是O(n log k)

为什么这是正确的？

假设不是。然后对于某些输入，我的算法给出了非最佳排序。设 I 为这样的输入，A 为我在 I 上的算法的输出，B 为最优排序。

设 i 是 A 和 B 不一致的第一个索引。设x = A[i], y = B[i], j为x在B中的索引。

我声称交换 B 中的 x 和 y 可以提高 B 的排序性，这是矛盾的。

因为 A 和 B 在 i 之前的位置相同，所以同一组 k+1 个元素有资格进入位置 i。因为我的算法选择 x 作为这些元素的最小值，所以我们知道 x 小于 y。我们也知道 j 大于 i。

当我们交换 B 中的 x 和 y 时会发生什么？

首先，请注意，排序的变化不受 i 左侧或 j 右侧任何事物的影响，因为它们相对于 x 和 y 的位置不会因交换而改变。

我们知道 i 和 j 之间没有小于 x 的元素，因为我的排序选择了最小的可用元素。因此 i 和 j 之间的所有元素至少与 x 一样大。

对于 i 和 j 之间等于 x 的每个元素，交换 x 和 y 将排序提高 1，因为我们相对于这些元素提高了 y 而 x 不受影响。

对于i和j之间每一个大于x的元素，x相对于这些的排序度提高1，最坏情况下y相对于这些的排序度降低1，所以净效果最差0.

此外，交换 x 和 y 将 x 相对于 y 的排序提高了 1，因此这种交换严格提高了整体排序。

矛盾。