问题描述:
设a[0:n-1]是一个有n个元素的数组，k(0<=k<=n-1)是一个非负整数．试设计一个算法将子数组
a[0:k]与a[k+1:n-1]换位．要求算法在最坏情况下耗时O(n), 且只用到O(1)的辅助空间．
这个问题比较常见了,一般的办法就是分别把两个子数组分别逆序排列,然后对整个数组进行逆序排列.也就是说,对一个数组
a[8] = {1,2,3,4,5}而言,如果k = 2,那么首先对两个子数组进行逆序操作得序列{3, 2,1,5,4},然后对整个数组逆序排列得到{4,5,1,2,3}.
下面给出的是另一种办法,采用的是递归方法,结合前面的例子讲述一下思想,在例子中前面的元素数量大于后面的元素数量(前面是3个,后面是两个),那么先以含有比较少的元素子数组的数量为标准进行交换,得到序列:{4,5,3,2,1},中间多出来的3没有参与到这次交换之中,这个时候含有比较少的元素的子数组{4,5}已经被交换到了最后合适的位置,后面的操作可以不必考虑它们了.对剩余子数组的操作显然和原来的问题有类似的行为,我们要做的是交换序列{3}和序列{2,1}的位置,因此这是一个递归可以解决的问题.
应该说,两种算法各有千秋吧.前一种办法最坏的时候每个元素都要移动两次才能到达最后合适的位置,但是第二种办法在两个数组元素数量相同的时候只需要移动一次元素就可以到达合适的位置了.
当然了,这个办法不如前一个方法那么"聪明",要写正确也不是很容易,但是可以作为分治法或者是递归法解决问题的一个实例.
#include <stdio.h>
void DisplayArray(int *pArray, int nLen)
{
for (int i = 0; i < nLen; ++i)
{
printf("array[%d] = %d\n", i, pArray[i]);
}
}
void SwapSubArray(int *pArray1, int *pArray2, int n)
{
int temp;
for (int i = 0; i < n; ++i)
{
temp = *(pArray1 + i);
*(pArray1 + i) = *(pArray2 + i);
*(pArray2 + i) = temp;
}
}
void ChangeArray(int *pArray, int nLen, int k)
{
if (NULL == pArray)
return;
if (k < 0 || k > nLen - 1)
return;
int m, n, num;
if (nLen - k - 1 > k + 1) // 如果后半部分的元素多
{
m = nLen - k - 1 - k - 1; // m是两部分元素数量之差
SwapSubArray(pArray, pArray + k + 1 + m, k + 1); // 交换两部分元素数目相同的部分
ChangeArray(pArray, nLen - k - 1, k);
}
else if (nLen - k - 1 < k + 1) // 如果前半部分的元素多
{
m = k + 1 - nLen + k + 1;
SwapSubArray(pArray, pArray + k + 1, k + 1 - m); // 交换两部分元素数目相同的部分
ChangeArray(pArray + nLen - k - 1, k + 1, m - 1);
}
else // 前后两部分元素数量相同
{
SwapSubArray(pArray, pArray + k + 1, k + 1);
}
}
int main()
{
int array[] = {0, 1, 2, 3, 4, 5, 6, 7};
int nLen = sizeof(array) / sizeof(array[0]);
DisplayArray(array, nLen);
ChangeArray(array, nLen, 1);
printf("after change:\n");
DisplayArray(array, nLen);
return 1;
}