习题－32.c

这些是数据结构结构的经典实现算法

//本程序只给出了算法思想
//读者可以自己完善本程序
//解答1：
void 	shaker_Sort ( ) {
	/*奇数趟对表Vector从前向后, 比较相邻的排序码, 遇到逆序即交换, 直到把参加比较排序码序列中最大的排序码移到序列尾部。偶数趟从后向前, 比较相邻的排序码, 遇到逆序即交换, 直到把参加比较排序码序列中最小的排序码移到序列前端。*/
	int i = 1, j;  int exchange;
	while ( i < CurrentSize ) {					//起泡排序趟数不超过n-1 
		exchange = 0;							//假定元素未交换
		for ( j = CurrentSize-i; j >= i; j-- )			//逆向起泡
			if ( Vector[j-1] > Vector[j] ) {				//发生逆序
				Swap ( Vector[j-1], Vector[j] );//交换, 最小排序码放在Vector[i-1]处
				exchange = 1;						//做"发生了交换"标志
			}
			if ( exchange == 0 )
				break;					//当exchange为0则停止排序
			for ( j = i; j <= CurrentSize-i-1; j++ )			//正向起泡
				if ( Vector[j] > Vector[j+1] ) {				//发生逆序
					Swap ( Vector[j], Vector[j+1] ); 	//交换, 最大排序码放在Vector[n-i]处
					exchange = 1;						//做"发生了交换"标志
				}
				if ( exchange == 0 )
					break;					//当exchange为0则停止排序
				i++;
	}
}
//解答2：
void shaker_Sort ( ) {
	int low = 1, high = CurrentSize-1, i, j;  
	int exchange;
	while ( low < high ) {//当比较范围多于一个对象时排序 
		j = low;								//记忆元素交换位置
		for ( i = low; i < high; i++ )					//正向起泡
			if ( Vector[i] > Vector[i+1] ) {				//发生逆序
				Swap ( Vector[i], Vector[i+1] );  			//交换
				j = i;				//记忆右边最后发生交换的位置j
			}
			high = j;						//比较范围上界缩小到j
			for ( i = high; i > low; i-- )				//反向起泡
				if ( Vector[i-1] > Vector[i] ) {				//发生逆序
					Swap ( Vector[i-1], Vector[i] );  			//交换
					j = i;					//记忆左边最后发生交换的位置j
				}
				low = j;							//比较范围下界缩小到j
	}
}