如果可以交换两个相等大小的子数组，则对数组进行排序所需的最小交换次数是多少？

Question

给定一个由正整数构成的数组 A[1...N]，您需要按照以下方式将其升序排序：在每个操作中，选择任意两个不重叠的等长子数组并交换它们。也就是说，选择两个子数组 A[i...(i+k-1)] 和 A[j...(j+k-1)]，使得 i+k-1<j 并交换 A[i] 和 A[j]，A[i+1] 和 A[j+1] ... 以及 A[i+k-1] 和 A[j+k-1]。

Example:
For N=6
6 7 8 1 2 3
Only one operation is needed as after swapping (6 7 8) and (1 2 3 ) sub arrays
we can get 1 2 3 6 7 8 , that is sorted.

我们如何以最有效的方式确定最小交换次数？ 来源：https://www.hackerearth.com/problem/approximate/swap-and-sort/

- Avaneesh Kumar

---

如果您将数组分解为在最终排序数组中字面上发生的运行，并为它们分配代表其等级的数字，则问题会简化为查找对于排序数组，进行1元素交换的最小次数。 - Niklas B.

这个问题很有趣，但请展示一下你的尝试。 - Abhishek Bansal

@Niklas B：你怎么知道通过移动多个运行的交换不能做得更好？此外，您是否假设可以交换不同长度的运行？ - Douglas Zare

任意两个单独的元素都是“长度相等的2个不重叠子数组”，不是吗？这将把问题简化为众所周知的排序算法之一。但也许这并不完全符合问题的本意... - twalberg

你可以通过2次交换得到6个对象的排列，其行形式为365214：1[23][45]6 -> [14]52[36] -> 365214。所有运行长度均为1，并且没有任何一个对象在其原始位置上，因此至少需要3次交换（我认为可能更多）才能将其恢复到标识状态，而不会组合或分解运行。 - Douglas Zare

Answer 1

#include <iostream>
using namespace std;

void swaparr(int a[],int l,int r,int n) {
    for(int i=l,j=r;i<=l+n&&j<=r+n;i++,j++)
        swap(a[i],a[j]);
}
int findMax(int a[],int n) {
    int index = 0;
    for(int i=1;i<=n;i++)
        if(a[i] > a[index])
            index = i;
    return index;
}
void sort(int a[],int n) {
    for(int r=n-1;r>;0;r--) {
        int index = findMax(a,r);
        if(index != r) {
            int l = min(r-index-1,index);
            swaparr(a,index-l,r-l,l);
        }
    }
}
int main() {
    int a[] = {7,23,8,234,3,6,41,334};
    int n = 8;
    sort(a,n);
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
    return 0;
}

逻辑: 在每次操作中找到最大的元素，并执行交换，使得最大的元素移到末尾。每次操作将数组大小减少一次，并旨在在每次操作中拥有最大的元素。并不一定需要进行N次交换。只有当最大元素不在其位置时才执行交换。时间复杂度为T = O(n2)。

- Love Bisaria