有限制条件下的整数排序

Question

如果我们有一个整数数组，那么我们如何确定将它们排序（按升序排列）所需的最小步骤，如果允许的每个步骤仅是：将元素移动到任一极端？例如，如果我们有 7 8 9 11 1 10 那么在第一步中可以将11移动到右端，在第二步中将1移动到左端以获得1 7 8 9 10 11。因此总步骤= 2。冒泡排序是否适用于此处？但最坏情况下的复杂性将是O（n ^ 2）。那么我们该如何更有效地处理呢？谢谢。

- pranay

Answer 1

这里有一个解决方案，它需要O(n log n)的时间复杂度，O(n)的辅助空间，并且正好需要n个MoveToFront操作。

给定输入数组A，创建第二个数组B，其中包含值/索引对，如下所示...

7 8 9 11 1 10  ->  (7 0) (8 1) (9 2) (11 3) (1 4) (10 5)
[this step takes O(n) time and O(n) space]

然后按每对值的降序对B进行排序...

(7 0) (8 1) (9 2) (11 3) (1 4) (10 5) -> (11 3) (10 5) (9 2) (8 1) (7 0) (1 4)
[this step takes O(n log n) time]

准备一个二叉搜索树T。

现在，对于B中的每个元素，请执行以下操作...

Let I be the index of this element.
Let V be the sum of I and the number of elements in T that are greater than I.
Do a MoveToFront operation on the Vth element of A.
Add I to T.
[Both of the operations on T take O(log n) time]

这个算法正在处理你的示例数组。

(11 3)
    I := 3
    V := 3 + 0 = 3
    MoveToFront(3): 7 8 9 11 1 10  ->  11 7 8 9 1 10
    T: ()  ->  (3)

(10 5)
    I := 5
    V := 5 + 0 = 5
    MoveToFront(5): 11 7 8 9 1 10  ->  10 11 7 8 9 1
    T: (3)  ->  (3 5)

(9 2)
    I := 2
    V := 2 + 2 = 4
    MoveToFront(4): 10 11 7 8 9 1  ->  9 10 11 7 8 1
    T: (3 5)  ->  (2 3 5)

(8 1)
    I := 1
    V := 1 + 3 = 4
    MoveToFront(4): 9 10 11 7 8 1  ->  8 9 10 11 7 1
    T: (2 3 5)  ->  (1 2 3 5)

(7 0)
    I := 0
    V := 0 + 4 = 4
    MoveToFront(4): 8 9 10 11 7 1  ->  7 8 9 10 11 1
    T: (1 2 3 5)  ->  (0 1 2 3 5)

(1 4)
    I := 4
    V := 4 + 1 = 5
    MoveToFront(5): 7 8 9 10 11 1  ->  1 7 8 9 10 11
    T: (0 1 2 3 5)  ->  (0 1 2 3 4 5)

我想你可以找到一些使用少于n个MoveToFront/Back操作的方法来对这些数组进行排序，但我认为你不能在少于O(n log n)的时间内找到这些方法。然而，如果这些操作很慢，那么使用一个需要更长时间规划但可以减少这些操作次数的算法可能是值得的。

- Running Wild

---

这并没有解决问题，因为作者的例子返回2，但你的似乎返回5。我有什么遗漏吗？ - Archeg

作者询问我们是否可以比n^2的MoveToFront/Back操作更有效地对数组进行排序。我在这里展示，如果我们花费O(n log n)的时间，我们可以用n次MoveToFront/Back操作来完成它，我假设除非花费超过O(n log n)的时间，否则我们无法做得更好。 - Running Wild

不错。这让我想起了我曾经用类似的树结构解决过的 http://www.spoj.pl/problems/YODANESS/ 问题。（虽然我也可以使用范围树） - Rusty Rob

我认为我们可以找到逆序对的数量，并在那里添加一些限制？ - pranay

Answer 2

你能稍微澄清一下这个问题吗？当你说列表时，是指链表还是数组？如果不是链表，我对有限的操作集有点困惑。如果是链表，你可以修改快速排序算法，它的平均时间复杂度为O(nlgn)。

- vpiTriumph

Answer 3

基本上，您提到的数据结构是链表。对于链表，您可以使用快速排序或归并排序（O（nlogn））。

- ElKamina

Answer 4

那听起来不像是一个排序问题。你只需要找出需要移动多少个元素，但你不需要对数组进行排序。我敢打赌这可以比O(n log n)更快地完成。

我提出以下解决方案：只需计算有多少个a[i] > a[i-1]，这将是你的结果。

论证：

如果你有a[i] > a[i-1]，这意味着a[i]或a[i-1]中的至少一个不在它们应该在的位置上。所以你可以：

1）将a[i-1]移到数组的开头

2）将a[i]移到数组的末尾。

更新：你需要确定移动哪个a[i]或a[i-1]，例如对于数组7 8 9 11 1 10，你有两个比较结果表明哪些元素不在其位置上：11 > 1和11 > 10。所以这肯定是一个动态规划的任务。但是，它仍然比O(n log n)更快。

- Archeg