鸡尾酒排序

　也就是定向冒泡排序, 鸡尾酒搅拌排序, 搅拌排序 (也可以视作选择排序的一种变形), 涟漪排序, 来回排序 or 快乐小时排序, 是冒泡排序的一种变形。此演算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。

 

 

public class Cocktail {
	int[] list = {88,23,1,23,2,9,10};
	
	void sort(){
		int length = list.length;
		boolean flag=true;
		while(flag){
			flag=false;
			for(int i = 0 ; i < length-1;i++){  //从低处往高处比较
				if(list[i]>list[i+1]){
					int temp = list[i];
					list[i] = list[i+1];
					list[i+1]= temp;
					
					flag = true;
				}
			}
			length--;
			for(int i = length-1; i > 0; i--){   //从高处往低处比较

				if(list[i]<list[i+1]){
					int temp = list[i];
					list[i] = list[i-1];
					list[i-1]= temp;
					flag = true;
				}
			}
		}
	}
	
	void print(){
		for(int i = 0 ; i < list.length ;i++){
			System.out.println(list[i]);
		}
	}
	public static void main(String[] args) {
		Cocktail c = new Cocktail();
		c.sort();
		c.print();
	}
}

 

 

鸡尾酒排序等于是冒泡排序的轻微变形。不同的地方在于从低到高然后从高到低，而冒泡排序则仅从低到高去比较序列里的每个元素。他可以得到比冒泡排序稍微好一点的效能，原因是冒泡排序只从一个方向进行比对(由低到高)，每次循环只移动一个项目。

　　以序列(2,3,4,5,1)为例，鸡尾酒排序只需要访问一次序列就可以完成排序，但如果使用冒泡排序则需要四次。

　　复杂度

　　鸡尾酒排序最糟或是平均所花费的次数都是O(n2)，但如果序列在一开始已经大部分排序过的话，会接近O(n)。