如何通过反转子序列对排列进行排序（取自 Skiena 第 3 版）
How to sort a permutation by reversing subsequences (taken from Skiena 3rd ed.)
在过去的 24 小时里，我一直被 Skiena（算法设计手册，第 3 版）提出的以下问题的第二部分所困，快把我逼疯了！在这一点上，我正在努力想出新的想法，并希望得到一些 tips/solutions.
练习 4-27
假设给定整数 1 到 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. 设计一个算法，排序 p in O(nlog^2n) cost.
如果我们对它进行暴力破解，第一部分看起来相当简单：找到 largest/smallest 值的位置并反转将其放置在正确位置的子序列。对下一个 largest/smallest 值重复，直到序列的顺序正确。显然，这最多需要 n 个反转。
但是如果我将这种蛮力方法应用于问题的第二部分，那么在最坏的情况下成本似乎可能是 O(n^2)设想。有人有什么建议吗？
有一种适合就地归并排序的算法：
- 对数组的前半部分进行排序；
- 对数组的后半部分进行排序；
- 就地合并两半。
合并需要 O(N log N) 时间：
- 确定属于下半部分的前半部分元素个数；
- 将上半部分最后的元素与下半部分的第一个元素交换。你可以用 3 个反转来做到这一点
- 递归合并前半段和后半段的2个片段
由于合并需要 O(N log N) 时间，所以整个排序需要 O(N log2 N) 时间。
我正在为 Matt Timmermans 的出色回答提供更多注释，以防将来有人需要更多详细信息（就像我一样）。
假设我们有两个排序序列 a_1 < ... < a_n 和 b_1 < .. . < b_n。我们想将这两个序列合并成一个排序序列 c_1 < ... < c_{2n}。我们首先找到最大的 k 使得 b_1, ..., b_k 在 n 最终排序集中的最小值。我们可以在 O(2n) 中做到这一点。通过对称性，a_{n-k+1}, ..., a_n 必须在 n 中的最大值最终排序集。
我们可以用逆运算来交换a_{n-k+1}, ..., a_n and b_1, ..., b_k 成本 O(2k)。我们现在有 4 个序列：a_1 < ... < a_{n-k}, b_k > ... > b_1, a_n > ... > a_{n-k+1} 和 b_{k+1} < .. . < b_n。序列 b_k, ..., b_1 和 a_n, ..., a_{n-k+1 }由于原先的逆运算，顺序倒序。因此，我们对两个序列应用另一个反向操作以正确排序它们。这花费了 O(2k).
我们现在已经将原始问题的大小减半，成本约为 O(n)。我们减少的问题是合并有序序列 a_1 < ... < a_{n-k} 和 b_1 < ... < b_k，还要合并有序序列 a_{n-k+1} < ... < a_n 和 b_{k+1} < ... < b_n。序列簿记在这一点上有点毛茸茸，但考虑 k=n/2 的特殊情况有助于了解一般方法。
对于k=n/2，我们的情况与我们的原始问题（两个大小相等的排序序列）相同，除了我们现在有两对序列，每个都是我们原来问题长度的一半。所以我们可以在这些新的序列对上重复我们解决原始问题的方法。这将再次将我们问题的规模一分为二，成本为 2O(n/2)。一般来说，对于 2^m 对长度为 n/2^m 的有序序列，成本将为 2^m O(n/2^m) 即 O(n).
通过将我们的问题重复拆分为 2 倍并且每次拆分的成本为 O(n)，我们看到这种递归方法将使我们能够合并我们的问题成本最多为 O(n logn).
的原始序列
因此我们可以使用反向操作合并两个长度为 n 的有序序列，成本最多为 O(n logn)。通过应用另一种递归方法（如传统排序算法），我们发现我们可以对 O(n log^2n).
中的任意顺序序列进行排序
在过去的 24 小时里，我一直被 Skiena（算法设计手册，第 3 版）提出的以下问题的第二部分所困，快把我逼疯了！在这一点上，我正在努力想出新的想法，并希望得到一些 tips/solutions.
练习 4-27 假设给定整数 1 到 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. 设计一个算法，排序 p in O(nlog^2n) cost.
如果我们对它进行暴力破解，第一部分看起来相当简单：找到 largest/smallest 值的位置并反转将其放置在正确位置的子序列。对下一个 largest/smallest 值重复，直到序列的顺序正确。显然，这最多需要 n 个反转。
但是如果我将这种蛮力方法应用于问题的第二部分，那么在最坏的情况下成本似乎可能是 O(n^2)设想。有人有什么建议吗？
有一种适合就地归并排序的算法：
- 对数组的前半部分进行排序；
- 对数组的后半部分进行排序；
- 就地合并两半。
合并需要 O(N log N) 时间：
- 确定属于下半部分的前半部分元素个数；
- 将上半部分最后的元素与下半部分的第一个元素交换。你可以用 3 个反转来做到这一点
- 递归合并前半段和后半段的2个片段
由于合并需要 O(N log N) 时间，所以整个排序需要 O(N log2 N) 时间。
我正在为 Matt Timmermans 的出色回答提供更多注释，以防将来有人需要更多详细信息（就像我一样）。
假设我们有两个排序序列 a_1 < ... < a_n 和 b_1 < .. . < b_n。我们想将这两个序列合并成一个排序序列 c_1 < ... < c_{2n}。我们首先找到最大的 k 使得 b_1, ..., b_k 在 n 最终排序集中的最小值。我们可以在 O(2n) 中做到这一点。通过对称性，a_{n-k+1}, ..., a_n 必须在 n 中的最大值最终排序集。
我们可以用逆运算来交换a_{n-k+1}, ..., a_n and b_1, ..., b_k 成本 O(2k)。我们现在有 4 个序列：a_1 < ... < a_{n-k}, b_k > ... > b_1, a_n > ... > a_{n-k+1} 和 b_{k+1} < .. . < b_n。序列 b_k, ..., b_1 和 a_n, ..., a_{n-k+1 }由于原先的逆运算，顺序倒序。因此，我们对两个序列应用另一个反向操作以正确排序它们。这花费了 O(2k).
我们现在已经将原始问题的大小减半，成本约为 O(n)。我们减少的问题是合并有序序列 a_1 < ... < a_{n-k} 和 b_1 < ... < b_k，还要合并有序序列 a_{n-k+1} < ... < a_n 和 b_{k+1} < ... < b_n。序列簿记在这一点上有点毛茸茸，但考虑 k=n/2 的特殊情况有助于了解一般方法。
对于k=n/2，我们的情况与我们的原始问题（两个大小相等的排序序列）相同，除了我们现在有两对序列，每个都是我们原来问题长度的一半。所以我们可以在这些新的序列对上重复我们解决原始问题的方法。这将再次将我们问题的规模一分为二，成本为 2O(n/2)。一般来说，对于 2^m 对长度为 n/2^m 的有序序列，成本将为 2^m O(n/2^m) 即 O(n).
通过将我们的问题重复拆分为 2 倍并且每次拆分的成本为 O(n)，我们看到这种递归方法将使我们能够合并我们的问题成本最多为 O(n logn).
的原始序列因此我们可以使用反向操作合并两个长度为 n 的有序序列，成本最多为 O(n logn)。通过应用另一种递归方法（如传统排序算法），我们发现我们可以对 O(n log^2n).
中的任意顺序序列进行排序