【排序算法】鸡尾酒排序的实现与分析

以升序排序为例：

算法思路

鸡尾酒排序即双向的冒泡排序，是冒泡排序的轻微变形。

它的主要思路是对于一组无规律排放的数字，先找到最大的数字放到最后一位，在反向找到最小的数字放到第一位。然后再找第二大的数字放到倒数第二位，再找第二小的数字放到第二位。以此类推，直到所有数字有序排列。

代码实现

public class CocktailSort {public static void main(String args[]) {  int[] numbers={-1, 0, 50, 44, -90};sort(numbers);for(int number : numbers) { System.out.println(number); } }static void sort(int[] numbers){int temp;int m=0,n=numbers.length-1;while(m<n){for(int i=m; i<n;i++){if(numbers[i]>numbers[i+1]){//交换数组中两个数字的位置temp=numbers[i];numbers[i]=numbers[i+1];numbers[i+1]=temp;}}n--;for(int i=n; i>m;i--){if(numbers[i]<numbers[i-1]){//交换数组中两个数字的位置temp=numbers[i];numbers[i]=numbers[i-1];numbers[i-1]=temp;}}m++;}}}

• 复杂度分析

  对于鸡尾酒排序，算法的时间复杂度与空间复杂度显然与上一篇的冒泡排序相同。

  不同的是排序的交换次数。某些情况下鸡尾酒排序比普通冒泡排序的交换次数少。比如{2,3,4,1},鸡尾酒排序只需交换2次，而冒泡排序需要三次。

  总体上，鸡尾酒排序可以获得比冒泡排序稍好的性能。但是完全逆序时，鸡尾酒排序与冒泡排序的效率都非常差。