algorithm - 如何通过反转子序列对排列进行排序(取自 Skiena 第 3 版)

Question

在过去的 24 小时里，我一直在回答 Skiena(算法设计手册，第 3 版)提出的以下问题的第二部分，这让我抓狂!目前我正在努力想出新的想法，希望能提供一些提示/解决方案。

练习 4-27 假设给定一个从 n 到 n 的整数排列 p，然后寻找 将它们排序为递增顺序 [1, . . . , n]。您唯一的操作 处置是reverse(p,i,j)，它反转子序列(p_i, ..., p_j)的元素 在排列中。对于排列 [1, 4, 3, 2, 5] 一个反转(第二个 通过第四个元素)足以排序。

• 证明可以使用 O(n) 次反转对任何排列进行排序。
• 现在假设 reverse(p,i,j) 的成本等于它的长度，范围内的元素数量，|j − i| + 1. 设计一种算法，以 O(nlog^2n) 成本对 p 进行排序。

如果我们对它进行暴力破解，那么第一部分看起来相当简单:定位最大/最小值的位置并反转将其放置在正确位置的子序列。重复下一个最大/最小值，直到序列顺序正确。显然，这最多需要 n 个逆转。

但如果我将这种蛮力方法应用于问题的第二部分，在最坏的情况下，成本似乎可能是 O(n^2)。有人有什么建议吗？

Answer 1

有一个就地归并排序算法适合:

1. 对数组的前半部分进行排序；
2. 对数组的后半部分进行排序；
3. 就地合并两半。

合并需要 O(N log N) 时间:

1. 确定属于下半部分的前半部分元素个数；
2. 将前半部分的最后元素与后半部分的前几个元素交换。你可以通过 3 个反转来做到这一点
3. 递归合并前半部分和后半部分的两部分

由于合并需要 O(N log N) 时间，所以整个排序需要 O(N log² N) 时间。