Hark的数据结构与算法练习之鸡尾酒排序

算法说明

鸡尾酒排序又叫定向冒泡排序,鸡尾酒搅拌排序,搅拌排序,涟漪排序,回来排序,快乐小时排序。

鸡尾酒排序是交换排序的一种,它是冒泡排序的一个轻微的变种。冒泡是从低向高比较排序,鸡尾酒从低向高,从高向低交换着进行排序。大家看一下代码就知道了。

某些特殊有序数组情况下,鸡尾酒排序是效率略好于冒泡排序,例如:

int[] arrayData = { 2, 3, 4, 5, 6, 7, 8, 9, 1 };

鸡尾酒排序只排序一次就能出结果,而冒泡排序就需要8次才能出结果。

代码

使用的是java

package hark.sort.exchangesort;

/*
* 鸡尾酒排序
*/
public class CocktailSort {
public static void main(String[] args) {
int[] arrayData = { 2, 3, 4, 5, 6, 7, 8, 9, 1 };
CocktailSortMethod(arrayData);
for (int integer : arrayData) {
System.out.print(integer);
System.out.print(" ");
}
} public static void CocktailSortMethod(int[] arrayData) {
boolean swapped = true;
int bottom, top, temp;
top = arrayData.length - 1;
bottom = 0;
while (swapped) {
swapped = false; // 从左向右进行排序
for (int i = bottom; i < top; i++) {
if (arrayData[i] > arrayData[i + 1]) {
temp = arrayData[i];
arrayData[i] = arrayData[i + 1];
arrayData[i + 1] = temp;
swapped = true;
}
}
top -= 1; // 因为已经把最大值移动到最右侧了,所以top=top-1 // 从右向左进行排序
for (int i = top; i > bottom; i--) {
if (arrayData[i] < arrayData[i - 1]) {
temp = arrayData[i];
arrayData[i] = arrayData[i - 1];
arrayData[i - 1] = temp;
swapped = true;
}
}
bottom += 1; // 因为已经把最小值移动到最右侧了,所以bottom=bottom+1
}
}
}

结果

1 2 3 4 5 6 7 8 9 

参考

http://zh.wikipedia.org/wiki/%E9%B8%A1%E5%B0%BE%E9%85%92%E6%8E%92%E5%BA%8F

上一篇:【转】图说Android的8年演变史


下一篇:【ERROR】---Error executing "adb devices":ADB server didn't ACK