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