[程式設計珠玑題目] 一維向量左旋轉

最近太忙了買了程式設計珠玑之後就翻過2頁，今天正好@neiddy 問我看裡面的題目，就花了點時間看看做一下。自己思考後跟書上講的第二種有效方法很想，考慮後就在想執行效率，是以寫了代碼來看一下，最後需要做⌈ length/rotatelength⌉ or +1（就不寫那麼複雜了）次此swap，每次swap做routateLength次交換，是以時間複雜度是O(n)，空間複雜度O(1)。其實第一種實作思路較為直覺，開始思考了這樣的替換，覺着複雜沒有深入思考，其實也是很好的方法，時間複雜度低。看到第三種方法的時候就覺着自己弱爆了，好吧，說題目吧，我實作了第二種。懷着羨慕嫉妒恨寫了第三種漂亮的算法。

說明：

因為每個循環交換需要用到一次temp，後兩個算法每個循環隻有2個值，但是雜技算法那這個每個循環可能有很多，是以減少了對temp的指派次數，帶來一定的性能提升（這裡說的如果每個部分都是大資料的話 （糾正這個錯誤，實際的實作中肯定隻會做位址的指派，即便是大資料不可能做關于記憶體塊的移動，是以這部分雖然減少了交換次數，但是由于下面提到的取餘指令問題依然造成了性能的衰減，但是不會很明顯，也不是在算法分析中需要太關注的環節，但是如果必須做記憶體塊交換或外存空間的話需要謹慎選擇算法，并盡量考慮使用其他的方法解決這個限制），如果隻是交換char的話取餘數并指派為四條指令，遠比加減和指派多，是以性能反而得不到提升，這都屬于細節了，如果真的是用大資料的話就要考慮犧牲一定的可讀性了）。

題目：（原書11頁問題B）

将一個n元一維向量向左旋轉i個為孩子。例如，當n=8且i=3時，向量abcdefgh左旋轉為defghabc。簡單的代碼使用一個n元的中間向量在n步完成該工作。你能否使用數十個額外位元組的存儲空間，在正比于n的時間内完成向量的旋轉？

by me，第二種實作方法

/*
 * vectorrotate.c
 *
 *  Created on: Dec 17, 2012
 *      Author: Jason_wbw
 */

#include <stdio.h>
#include <string.h>

/**
 * 交換vector中的兩部分：
 * 交換前的四部分[firstBegin, firstBegin+swapLength-1],
 *              [firstBegin+swapLength, secondBegin-1],
 *              [secondBegin, secondBegin+swapLength-1],
 *              [secondBegin+swapLength, end]
 * 交換内容為第一和第三部分，交換後如下
 *              [secondBegin, secondBegin+swapLength-1],
 *              [firstBegin+swapLength, secondBegin-1],
 *              [firstBegin, firstBegin+swapLength-1],
 *              [secondBegin+swapLength, end]
 */
void swapVector(char* vector, int firstBegin, int secondBegin, int swapLength){
	char temp;
	int i;
	for(i=0; i<swapLength;i++){
		temp = vector[firstBegin+i];
		vector[firstBegin+i] = vector[secondBegin+i];
		vector[secondBegin+i] = temp;
	}
}

/**
 * 向量的左旋轉
 * 算法如下：
 * 按照position将vector分成ab兩部分，最終需要變成ba。
 * [1]若a長度小于b，将b分為b1b2，其中b2長度等于a。交換a和b2變為b2b1a，再遞歸傳回到判斷修改b2b1為b1b2。
 * [2]若a長度大于b，将a分為a1a2，其中a1長度等于b。交換a2和b變為ba2a1，再遞歸傳回到判斷修改a2a1為a1a2。
 * [3]若a長度等于b，交換a、b，算法結束。
 *
 * 'vector'   要旋轉的字元串數組
 * 'position' 旋轉幾個位置
 *
 * return 0 表示position越界；1 表示成功左旋轉
 */
int route(char* vector, int position){
	if(position<=0 || position>=strlen(vector)){
		return 0;
	}

	int firstPosition = 0;                          //算法判斷情況[1]中a的首位址
	int headerLength = position;                    //算法判斷情況[1]中a的長度
	int enderLength = strlen(vector)-position;      //算法判斷情況[1]中b的長度

	while(headerLength!=enderLength){
		if(headerLength<enderLength){            //算法判斷情況[1]
			swapVector(vector, firstPosition, firstPosition+enderLength, headerLength);
			enderLength -= headerLength;
		}else{                                   //算法判斷情況[2]
			swapVector(vector, firstPosition, firstPosition+headerLength, enderLength);
			firstPosition = enderLength;
			headerLength -= enderLength;
		}
	}

	//算法判斷情況[3]
	swapVector(vector, firstPosition, firstPosition+headerLength, headerLength);

	return 1;
}

/**
 * test
 */
int main(){

	char vector[8] = {'a','b','c','d','e','f','g','h'};
	printf("before rotate : %s\n",vector);
	int result = route(vector,3);
	if(result==1){
		printf("after rotate : %s",vector);
	}
	return 0;
}
      

羨慕嫉妒恨的漂亮算法：

/*
 * beautiful_rotate.c
 *
 *  Created on: Dec 18, 2012
 *      Author: Jason_wbw
 */

#include <stdio.h>

/**
 * 将vector逆序，比如vector為abcde，逆序後為edcba
 */
void reverse(char* vector, int begin, int end){
	while(begin < end){
		char temp = vector[begin];
		vector[begin] = vector[end];
		vector[end] = temp;
		begin++;
		end--;
	}
}

/**
 * test
 * 測試左旋轉位數為3，先對0-2進行逆序，再對3-7逆序，最後整體逆序完成了從ab序列變成ba序列
 */
int main(){

	char vector[8] = {'a','b','c','d','e','f','g','h'};
	printf("before rotate : %s\n",vector);
	reverse(vector, 0, 3-1);
	reverse(vector, 3, 8-1);
	reverse(vector, 0, 8-1);
	printf("after rotate : %s",vector);
	return 0;
}

           

by @neiddy 實作的第一種書上叫做雜技的算法，很好了解。這種算法每次循環隻需要給temp（代碼中的buffer做一次指派，可以減少指派的次數）

#include <stdio.h>

void string_rotate( char* str, int len, int n )
{
	int i = 0;
	int cnt = 0;
	n %= len;
	for ( i = 0; i < n && cnt < len; i++ )
	{
		int index = i;
		char buf = str[i];
		while (1)
		{
			int temp = ( index + n ) % len;
			cnt++;
			if ( temp == i )
			{
				str[index] = buf;
				break;
			}
			else 
			{
				str[index] = str[temp];
			}
			index = temp;
		}
	}
}

int main ( void )
{
	char str[] = "12345678";
	string_rotate( str, 5, 2 );
	printf("%s\n",str);
}