1 鸡尾酒排序

鸡尾酒排序是冒泡排序的一种变形。它与冒泡排序的不同之处在于排序时是以双向在序列中进行排序。

2 原理

鸡尾酒排序的原理跟冒泡排序差不多，只不过冒泡排序每一轮的比较都是从左至右依次比较，而鸡尾酒排序则是一轮从左至右比较，下一轮从右至左比较。

假如有一个这样的数组：{2, 3, 4, 5, 6, 7, 8, 1}，如果按照冒泡排序的比较方式，会是这样的流程：

可以看到其实每次移动的只是元素 1，如果按照冒泡排序的原理，一共需要进行 7 轮比较，显然这是可以进行优化的，在第 1 轮比较后，第 2 轮则从右至左比较，将最小的元素交换到最左侧，这样就可以减少比较的总次数：

3 代码实现

    public static int[] cockTailSort1(int[] origin) {if (origin == null || origin.length == 0) {return new int[]{};}System.out.println("origin--->" + Arrays.toString(origin));int index = 0;for (int i = 0; i < origin.length - 1; i++) {boolean isSorted = true;if (i % 2 == 0) {for (int j = 0; j < origin.length - i - 1; j++) {if (origin[j] > origin[j + 1]) {int temp = origin[j];origin[j] = origin[j + 1];origin[j + 1] = temp;isSorted = false;}index++;}} else {for (int j = origin.length - i - 1; j > 0; j--) {if (origin[j - 1] > origin[j]) {int temp = origin[j - 1];origin[j - 1] = origin[j];origin[j] = temp;isSorted = false;}index++;}}System.out.println("第" + (i + 1) + "次比较后" + "--->" + Arrays.toString(origin) + ",isSorted--->" + isSorted);if (isSorted) {break;}}System.out.println("index--->" + index);System.out.println("sortedArray--->" + Arrays.toString(origin));return origin;}

使用测试代码运行一遍：

    @Testpublic void testCockTailSort1() {// int[] intArray = new int[10];// for (int i = 0; i < intArray.length; i++) {// intArray[i] = new Random().nextInt(100);// }int[] intArray = new int[]{2, 3, 4, 5, 6, 7, 8, 1};cockTailSort1(intArray);}

运行结果如下：

可以看到相较于冒泡排序，总的比较次数已经从 8 次减少到了 3 次。

4 优化

同样，鸡尾酒排序也可以像冒泡排序一样进行优化，记录左右比较位置，减少内循环次数：

    public static int[] cockTailSort(int[] origin) {if (origin == null || origin.length == 0) {return new int[]{};}// 记录右侧最后一次交换的位置int lastRightExchangeIndex = 0;// 记录左侧最后一次交换的位置int lastLeftExchangeIndex = 0;// 无序数列的右边界，每次比较只需要比到这里为止int rightSortBorder = origin.length - 1;// 无序数列的左边界，每次比较只需要比到这里为止int leftSortBorder = 0;System.out.println("origin--->" + Arrays.toString(origin));int index = 0;for (int i = 0; i < origin.length - 1; i++) {boolean isSorted = true;if (i % 2 == 0) {System.out.print("从 " + leftSortBorder + " 比较到 " + rightSortBorder + ",");for (int j = leftSortBorder; j < rightSortBorder; j++) {if (origin[j] > origin[j + 1]) {int temp = origin[j];origin[j] = origin[j + 1];origin[j + 1] = temp;isSorted = false;lastRightExchangeIndex = j;}index++;}} else {System.out.print("从 " + rightSortBorder + " 比较到 " + leftSortBorder + ",");for (int j = rightSortBorder; j > leftSortBorder; j--) {if (origin[j] < origin[j - 1]) {int temp = origin[j];origin[j] = origin[j - 1];origin[j - 1] = temp;isSorted = false;lastLeftExchangeIndex = j;}index++;}}leftSortBorder = lastLeftExchangeIndex;rightSortBorder = lastRightExchangeIndex;System.out.println("第" + (i + 1) + "次比较后" + "--->" + Arrays.toString(origin) + ",isSorted--->" + isSorted);if (isSorted) {break;}}System.out.println("index--->" + index);System.out.println("sortedArray--->" + Arrays.toString(origin));return origin;}

运行结果如下：