排序算法（九）鸡尾酒排序

  鸡尾酒排序（Cock-Tail-Sort）是基于冒泡排序做一点点优化而来的。冒泡排序的原理：从第一个数开始，依次往后比较，相邻的元素两两比较，根据大小来交换元素的位置，如果前面的数比后面的数大就交换，否则不作处理。这就类似烧开水时，壶底的水泡往上冒的过程。这个过程中，元素是单向交换的，也就是说只有从左往右交换，而鸡尾酒排序的元素比较和交换过程是双向的。

图解过程

以数组：3, 4, 5, 6, 1为例，按从小到大的方式排序，冒泡排序的过程如下：
冒泡第一次循环

冒泡第一此循环
我们可以发现，在未开始排序的时候，前4个数已经是有序序列了，然而进行冒泡排序至少还需要循环四次、交换四次，这也太浪费时间了吧！
因此就有了鸡尾酒排序，先看看用鸡尾酒排序是怎么操作的，
鸡尾酒第一次循环*
鸡尾酒第一次循环
从上图可看出，本来需要四次循环，选择仅需一次即可，效率大大提高。
代码实现

public int[] sort() {
    int[] numbers = {3, 4, 5, 6, 1};
    for (int i = 0; i < numbers.length/2 - 1; i++) {

        // 从左往右遍历时，是否有交换操作的标志
        boolean isRightExchange = false;
        for (int j = 0; j < numbers.length - 1 - i; j++) {
            if (numbers[j] > numbers[j + 1]) {
                int temp = numbers[j];
                numbers[j] = numbers[j + 1];
                numbers[j + 1] = temp;
                isRightExchange = true;
            }
        }
        // 若没有交换操作，则说明序列已经成为有序序列，直接跳出循环
        if (!isRightExchange) {
            break;
        }

        // 从右到左遍历时，是否有交换操作额标志
        boolean isLeftExchange = false;
        for (int k = numbers.length - i - 2; k > i ;k--) {
            if (numbers[k] < numbers[k - 1]) {
                int temp = numbers[k];
                numbers[k] = numbers[k - 1];
                numbers[k -1] = temp;
                isLeftExchange = true;
            }
        }
        // 若没有交换操作，则说明序列已经成为有序序列，直接跳出循环
        if (!isLeftExchange) {
            break;
        }
    }
    return numbers;
}

我们知道，在冒泡排序中，可以针对有序区进行优化，鸡尾酒排序一样也是可以的。
要想优化，我们可以在每一轮排序的最后，记录下最后一次元素交换的位置，那个位置也就是无序数列的边界，再往后就是有序区了。
对于单向的冒泡排序，我们需要设置一个边界值，对于双向的鸡尾酒排序，我们需要设置两个边界值。请看代码：

 public int[] sort() {
    int[] numbers = {3, 4, 5, 6, 1};

    // 左侧最后一次交换元素的位置
    int lastLeftExchangeIndex = 0;
    // 左侧边界值
    int sortLeftBorder = 0;

    // 右侧最后一次交换元素的位置
    int lastRightExchangeIndex = 0;
    // 右侧的边界值
    int sortRightBorder = numbers.length - 1;

    for (int i = 0; i < numbers.length/2 - 1; i++) {
        // 从左往右遍历时，是否有交换操作的标志
        boolean isRightExchange = false;
        for (int j = sortLeftBorder; j < sortRightBorder; j++) {
            if (numbers[j] > numbers[j + 1]) {
                int temp = numbers[j];
                numbers[j] = numbers[j + 1];
                numbers[j + 1] = temp;
                // 说明有交换操作
                isRightExchange = true;
                // 记录左侧最后一次元素交换的位置
                lastRightExchangeIndex = j;
            }
        }
        // 设置最后一次交换元素的位置
        sortRightBorder = lastRightExchangeIndex;
        // 若没有交换操作，则说明序列已经成为有序序列，直接跳出循环
        if (!isRightExchange) {
            break;
        }

        // 从右到左遍历时，是否有交换操作额标志
        boolean isLeftExchange = false;
        for (int k = sortRightBorder; k > sortLeftBorder ;k--) {
            if (numbers[k] < numbers[k - 1]) {
                int temp = numbers[k];
                numbers[k] = numbers[k - 1];
                numbers[k -1] = temp;
                // 说明有交换操作
                 isLeftExchange = true;
                // 记录右侧最后一次元素交换的位置
                lastLeftExchangeIndex= k;
            }
        }
        // 设置最后一次交换元素的位置
        ortLeftBorder = lastLeftExchangeIndex;
        // 若没有交换操作，则说明序列已经成为有序序列，直接跳出循环
         if (!isLeftExchange) {
            break;
        }
    }
    return numbers;
}

最后说明

鸡尾酒排序适用于在大部分元素已经有序的情况下，其优点是能够在该情况下大大减少循环次数，而缺点则是代码有点多。。。