問題描述:
?設a[0:n-1]是一個有n個元素的數(shù)組，k(0<=k<=n-1)是一個非負整數(shù)．試設計一個算法將子數(shù)組
a[0:k]與a[k+1:n-1]換位．要求算法在最壞情況下耗時O(n), 且只用到O(1)的輔助空間．
這個問題比較常見了,一般的辦法就是分別把兩個子數(shù)組分別逆序排列,然后對整個數(shù)組進行逆序排列.也就是說,對一個數(shù)組
a[8] = {1,2,3,4,5}而言,如果k = 2,那么首先對兩個子數(shù)組進行逆序操作得序列{3, 2,1,5,4},然后對整個數(shù)組逆序排列得到{4,5,1,2,3}.
下面給出的是另一種辦法,采用的是遞歸方法,結合前面的例子講述一下思想,在例子中前面的元素數(shù)量大于后面的元素數(shù)量(前面是3個,后面是兩個),那么先以含有比較少的元素子數(shù)組的數(shù)量為標準進行交換,得到序列:{4,5,3,2,1},中間多出來的3沒有參與到這次交換之中,這個時候含有比較少的元素的子數(shù)組{4,5}已經(jīng)被交換到了最后合適的位置,后面的操作可以不必考慮它們了.對剩余子數(shù)組的操作顯然和原來的問題有類似的行為,我們要做的是交換序列{3}和序列{2,1}的位置,因此這是一個遞歸可以解決的問題.
應該說,兩種算法各有千秋吧.前一種辦法最壞的時候每個元素都要移動兩次才能到達最后合適的位置,但是第二種辦法在兩個數(shù)組元素數(shù)量相同的時候只需要移動一次元素就可以到達合適的位置了.
當然了,這個辦法不如前一個方法那么"聰明",要寫正確也不是很容易,但是可以作為分治法或者是遞歸法解決問題的一個實例.
#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是兩部分元素數(shù)量之差
????????SwapSubArray(pArray,?pArray?+?k?+?1?+?m,?k?+?1);????????//?交換兩部分元素數(shù)目相同的部分
????????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);????????//?交換兩部分元素數(shù)目相同的部分
????????ChangeArray(pArray?+?nLen?-?k?-?1,?k?+?1,?m?-?1);
????}
????else????????????????????????????????????????????????????????//?前后兩部分元素數(shù)量相同
????{
????????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;
}