交换两个子数组的位置（只使用1个辅助空间）

一、问题描述

其实这是一个非常基本和常用的数组操作，它的描述如下：

有一数组X[0...n-1],现在把它发为两个子数组x1[0...m]和x2[m+1...n-1]，交换这两个子数组，使用数组x由x1x2变成x2x1，例如x={1，2，3，4，5，6，7，8，9}，x1={1，2，3，4，5}，x2={6，7，8，9}，交换后，x={6，7，8，9，1，2，3，4，5}。

二、解题思路

1、蛮力法

第一个想到的办法当然是用new或malloc开辟一个与其中一个子数组（如第一个子数组x1）大小的数组，并把此子数组的内容复杂到新开辟的数组中，然后把第二个数组x2的内容放到数组x的前面，再加新数组的内容（即x1的内容）复制到数组x的后面，所以空间复杂为O(n)，要扫描数组2次，即时间复杂度为O(N)。

2、平行移动法

这个方法有点类似于字符串的平行移动，这里以向左移动为例，我们可以把数组看成是环形的，每次用一个变量记录数组的第一个元素x[0]，把数组的全部元素向左移动一个单位，并把用变量记录的数据（即原先的x[0]）放到数组的最后一个位置。如此循环第一个子数组的元素的个数次，即把第一个子数组x1的元素全部移动到后面，就能把两个子数组交换。因为只用到了一个变量保存x[0]，所以空间复杂度为O(1)，而要把数组中的每个元素都移动第一个子数组的元素的个数次，设原数组的元素个数为N，则时间复杂度为O(N*(x1/x)*N) = O(N^2)。

3、分治法

既然我们不能一次把两个子数组交换，那么就先把分别两个子数组的内容交换，然后把整个数组的内容交换，即可得到问题的解，而交换两个变量的值，只需要使用一个辅助储存空间。其实这个非常好证明，就用上面的例子，自己算一算即可，证明如下：

交换两个数组后，x1={5，4，3，2，1}，x2={9，8，7，6}，即x={5，4，3，2，1，9，8，7，6}

交换整个数组后，x={6，7，8，9，1，2，3，4，5}

所以，空间复杂度为O(1)，扫描了两次数组，时间复杂度为O(n)。

三、代码实现

这里给出了第三种方法的实现代码，考虑到代码的通用性，使用了模板函数，如果看不懂模板函数，则只需要忽略template<typename T>，并把T看作是一个类型即可。代码如下：

template<typename T>
void SwapSubArray(T *array, int array_size, int div);


template<typename T>
void Swap(T *array, int left, int right);


template<typename T>
void SwapSubArray(T *array, int array_size, int div)
{
    //首先交换第一个子数组的内容
    Swap(array, 0, div);
    //再交换第二个子数组的内容
    Swap(array, div+1, array_size-1);
    //交换整个数组的元素
    Swap(array, 0, array_size-1);
}


template<typename T>
void Swap(T *array, int left, int right)
{
    //交换数组left到right的内容
    for(; left < right; ++left, --right)
    {
        T tmp = array[left];
        array[left] = array[right];
        array[right] = tmp;
    }
}

测试代码如下：

#include <iostream>
#include "swap_subarray.h"

using namespace std;

int main()
{
    int a[9] = {1,2,3,4,5,6,7,8,9};
    SwapSubArray(a, 9, 4);
    for(int i = 0; i < 9; ++i)
        cout << a[i];
    return 0;
}

运行结果如下：