排序算法值鸡尾酒排序(java)

一：概述

冒泡排序的每一个元素都可以像小气泡一样，根据自身的大小，一点一点地向着数组的一侧移动。算法的每一轮都是从左到右比较元素，进行单向的位置交换的。

鸡尾酒排序做了怎样的优化：

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

二：举例子

由9个数字组成的无序数列{2, 3, 4, 5, 6, 7, 1, 9, 8},对其我们希望从小到大的排序。

如果按照冒泡排序的思想，排序过程如下。

元素2，3，4，5，6，7，8，9都已经是有序的了，只有元素1的位置不对，却还要进行第8轮排序。

鸡尾酒排序就是解决这种问题的。

下面来说一说这个鸡尾酒排序的具体内容：

第一轮(和冒泡排序一样，8和9交换)

第二轮

此时开始不一样了，我们反过来从右向左比较进行交换。

第三轮(虽然实际上已经有序了，但是流程并没有结束)

在鸡尾酒排序的第三轮，需要重新从左向右比较进行交换。

1和2比较位置不变，2和3比较位置不变吗，3和4比较位置不变........6和7比较位置不变，7和8比较位置不变，8和9比较位置不变。

没有元素位置进行交换，证明已经有序，排序结束。

这就是鸡尾酒排序的思路。排序过程就像钟摆一样，第一轮从左向右，第2轮从右向左，第3轮从左向右....

鸡尾酒排序的代码实现如下：

 public static void sort(int array[]) {
        // 定义一个临时变量
        int tmp = 0;
        for (int i = 0; i < array.length / 2; i++) {
            // 有序标记，每一轮的初始值都是true
            boolean isSorted = true;
            // 奇数轮，从左向右比较和交换
            for (int j = i; j < array.length - i - 1; j++) {
                // 如果左边的元素大于右边的元素，则将该左边的元素赋值给临时变量
                if (array[j] > array[j + 1]) {
                    tmp = array[j];
                    // 再将右边的值赋值给左边的元素
                    array[j] = array[j + 1];
                    // 最后将临时变量的值，即左边元素的值赋值给右边的元素，达到交换值目的
                    array[j + 1] = tmp;
                    // 有元素交换，所以不是有序的，标记变为false
                    isSorted = false;
                }
            }
            // 如果是true就跳出整个循环
            if (isSorted) {
                break;
            }

            // 在偶数轮之前，将isSorted重新标记为true
            isSorted = true;
            // 偶数轮，从右向左比较和交换
            for (int j = array.length - i - 1; j > i; j--) {
                if (array[j] < array[j - 1]) {
                    tmp = array[j];
                    array[j] = array[j - 1];
                    array[j - 1] = tmp;
                    // 因为有元素交换，所以不是有序的，标记变为false
                    isSorted = false;
                }
                if (isSorted) {
                    break;
                }
            }
        }





    }


    public static void main(String[] args) {
        int[] array = new int[]{2, 3, 4, 5, 6, 7, 1, 9, 8};
//        int[] array = new int[]{2, 3, 4, 5, 6, 7,8, 1};
        sort(array);
        System.out.println(Arrays.toString(array));


    }


}

这段代码是鸡尾酒的原始实现。代码外层的大循环控制着所有的排序回合，大循环内包含两个小循环，第一个循环从左向右比较，第二个循环，从右向左比较元素并交换元素。