tengzhao201

最高效循環(huán)右移課程設計下載地址：
http://download.csdn.net/source/2296222

//最高效的循環(huán)右移算法！！
//這個是遞歸的寫法
//author:tengzhao201 QQ:715572192
//time:2010-4-24
//時間復雜度為O(n)，空間復雜度O(1)，交換點在中間時比逆序法快一倍！！！
//提速要點：由于取模運算的效率很低，去掉了取模運算后效率得到大提升；swap函數(shù)效率低，引入了temp變量
void TZshift1(int* arr,int N,int K)
{
K=K%N;

if(0==K)return;

int temp,qq,pp=0;
pp=0;qq=K;
for(int i=0;i<N-K;i++,pp++,qq++)
{
//swap(arr[i%K],arr[i+K]);//問題的關鍵在于找到原來的第i個元素現(xiàn)在在哪里，通過觀察可以發(fā)現(xiàn)在arr[i%K]的位置，下面的代碼實現(xiàn)了arr[i%K]和arr[i+K]的互換
if(K==pp)pp=0;
temp=arr[pp];
arr[pp]=arr[qq];
arr[qq]=temp;
}

TZshift1(arr,K,K-pp);
}

//最高效的循環(huán)右移算法！！
//非遞歸的寫法
//author:tengzhao201 QQ:715572192
//time:2010-4-24
//時間復雜度為O(n)，空間復雜度O(1)，交換點在中間時比逆序法快一倍！！！
//提速要點：采用非遞歸算法
void TZshift2(int* arr,int N,int K)
{
K=K%N;
if(0==K)
return;

//int count=0;
int temp,qq,pp=0;

while(K>0)
{
pp=0;qq=K;
for(int i=0;i<N-K;i++,pp++,qq++)
{
//swap(arr[i%K],arr[i+K]);//問題的關鍵在于找到原來的第i個元素現(xiàn)在在哪里，通過觀察可以發(fā)現(xiàn)在arr[i%K]的位置，下面的代碼實現(xiàn)了arr[i%K]和arr[i+K]的互換

if(K==pp)pp=0;
temp=arr[pp];
arr[pp]=arr[qq];
arr[qq]=temp;
//count+=2;
}
N=K;
if(0==pp)
return;
K-=pp;
//TZshift(arr,K,K-pp);
}
//cout<<"In tatal,has used "<<count<<" steps."<<endl;
}