排序(5) 鸡尾酒排序

发表于 | 分类于 | 阅读次数:

冒泡排序已经对算法进行有优化，但仍然不是最优。鸡尾酒排序又叫快乐小时排序，它基于冒泡排序又做了一点优化。博客中给出了鸡尾酒排序的优化版本。

鸡尾酒排序

原理

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

那么鸡尾酒排序做了怎样的优化呢？
鸡尾酒排序的元素比较和交换过程是 双向的。

举个例子：
有8个数组成一个无序数列 {2, 3, 4, 5, 6, 7, 8, 1}，希望从小到大排序

冒泡排序过程省略，可以看出来，需要将1进行7轮排序。

按照冒泡排序，事实上，2到8已经是有序了，只有元素1的位置不对，却还要进行7轮排序！！这明显不合理，需要改进。
而鸡尾酒排序正是要解决这种问题。

鸡尾酒排序过程

那么鸡尾酒排序又是什么样的？下面看看详细过程：

数列{2, 3, 4, 5, 6, 7, 8, 1}

第一轮（和冒泡排序一样，8和1交换）：
交换后 {2, 3, 4, 5, 6, 7, 1, 8}

第二轮：
反过来 从右往左比较和交换：

  • 8已经处于有序区，我们忽略掉8，让1和7比较。元素1小于7，所以1和7交换位置：{2, 3, 4, 5, 6, 1, 7, 8}
  • 接下来1和6比较，元素1小于6，所以1和6交换位置：{2, 3, 4, 5, 1, 6, 7, 8}
  • 接下来1和5比较，元素1小于5，所以1和5交换位置：{2, 3, 4, 1, 5, 6, 7, 8}
  • 接下来1和4交换，1和3交换，1和2交换，最终成为了下面的结果：
    {1, 2, 3, 4, 5, 6, 7, 8}

第三轮（虽然已经有序，但是流程并没有结束）：

  • 鸡尾酒排序的第三轮，需要重新从左向右比较和交换
  • 1和2比较，位置不变；2和3比较，位置不变；3和4比较，位置不变……6和7比较，位置不变。
  • 没有元素位置交换，证明已经有序，排序结束。

以上就是鸡尾酒排序的思路。排序过程就像钟摆一样，第一轮从左到右，第二轮从右到左，第三轮再从左到右……

原始实现

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

鸡尾酒排序java原始实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public class CockTailSort {
    public static void cockTailSort(int[] arr) {
        int tmp = 0;

        for (int i = 0; i < arr.length / 2; i++) {
            //有序标记，每一轮的初始是true
            boolean isSorted = true; 
            //奇数轮，从左向右比较和交换
            for (int j = i; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    //有元素交换，所以不是有序，标记变为false
                    isSorted = false;
                }
            }

            if (isSorted) {
                break;
            }

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

    public static void main (String[] args) {
        int[] list = {2, 32, 3, 34, 45, 8, 89, 20, 23, -1, -2, -3, -25};
        cockTailSort(list);
        for (int i: list)
            System.out.print(i + " ");
        System.out.println();            
    }
}

鸡尾酒排序进一步优化

在将冒泡排序的时候，有一种针对有序区的优化，鸡尾酒排序也可以根据这个思路来进行优化。

回顾一下冒泡排序针对有序区的优化思路：
原始的冒泡排序，有序区的长度和排序的轮数是相等的。比如第一轮排序过后的有序区长度是1，第二轮排序过后的有序区长度是2……

要想优化，我们可以在每一轮排序的最后，记录下最后一次元素交换的位置，那个位置也就是无序数列的边界，再往后就是有序区了。

对于单向的冒泡排序，我们需要设置一个边界值，对于 双向的鸡尾酒排序，我们需要设置两个边界值。

优化边界条件的鸡尾酒排序代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class CockTailSort {
    public static void cockTailSort(int[] arr) {
        int tmp = 0;

        int lastRightExchangedIndex = 0;    //记录右侧最后一次交换的位置
        int lastLeftExchangedIndex = 0;    //记录左侧最后一次交换的位置 

        //无序数列的右边界，每次比较只需要比到这里为止
        int rigthSortBorder = arr.length - 1;
        //无序数列的左边界，每次比较只需要比到这里为止
        int leftSortBorder = 0;

        for (int i = 0; i < arr.length / 2; i++) {
            boolean isSorted = true;
            //奇数轮，从左向右比较和交换
            for (int j = leftSortBorder; j < rigthSortBorder; j++) {
                if (arr[j] > arr[j + 1]) {
                    tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;

                    isSorted = false;
                    lastRightExchangedIndex = j;
                }
            }
            rigthSortBorder = lastRightExchangedIndex;
            if (isSorted) {
                break;
            }

            isSorted = true;
            //偶数轮，从右向左比较和交换
            for (int j = rigthSortBorder; j > leftSortBorder; j--) {
                if (arr[j] < arr[j - 1]) {
                    tmp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = tmp;

                    isSorted = false;
                    lastLeftExchangedIndex = j;
                }
            }
            leftSortBorder = lastLeftExchangedIndex;
            if (isSorted) {
                break;
            }
        }
    }
}

代码中使用了左右两个边界值，rightSortBorder 代表右边界，leftSortBorder代表左边界。

在比较和交换元素时，奇数轮从 leftSortBorder 遍历到 rightSortBorder 位置，偶数轮从 rightSortBorder 遍历到 leftSortBorder 位置。

复杂度及稳定性

鸡尾酒排序的优点是能够在特定条件下，减少排序的回合数；
缺点是，代码量几乎扩大了一倍。

至于能发挥出优势的场景，就是在 大部分元素已经有序 的情况下，比冒泡完美版还要好。

但是鸡尾酒排序即使优化了，时间复杂度也是O(n^2)，和冒泡排序的是时间复杂度相同。

0%