鸡尾酒排序(冒泡排序升级版)

 

参考：程序员小灰

冒泡排序每次都是从左到右来比较元素，进行单向的位置交换。

鸡尾酒排序的元素比较和交换过程都是双向的。

package chapter4.part2; import java.util.Arrays; import org.junit.Test; public class Cocktail { @Test public void test() { // int[] array = new int[] {2, 3, 4, 5, 6, 7, 8, 1}; // int[] array = new int[] {2, 3, 4, 5, 6, 7, 8, 10}; int[] array = new int[] {9, 3, 4, 5, 6, 7, 8, 1}; System.out.println("排序前： "+Arrays.toString(array)); int temp = 0; for(int i=0; i<array.length/2; i++) {//因为每走一回合，头尾的有序区会各增加一个元素，等于省一半的力，故i<array.length/2 boolean isSort = true; /* * 从右到左 */ for(int j=i; j<array.length-i-1; j++) { if(array[j]>array[j+1]) { temp = array[j]; array[j] = array[j+1]; array[j+1] = temp; isSort = false; } } if(isSort) { break; } /* * 从左到右 */ isSort = true;//重新标记，因为可能此回已然排好序 for(int j=array.length-i-1; j>i; j--) {//这里也可以优化成j=array.length-i-2;即从无序区的倒数第1个开始 if(array[j] < array[j-1]) { temp = array[j-1]; array[j-1] = array[j]; array[j] = temp; isSort = false; } } if(isSort) { break; } } System.out.println("排序后: "+Arrays.toString(array)); } }

测试用例：

鸡尾酒排序优点：在特定条件下，减少排序的回合数，而缺点就是代码量增加了1倍。

鸡尾酒排序能发挥优势的场景：大部分元素已经有序的情况。