普通的冒泡排序在排序１中已经进行了介绍，这片文章算是对冒泡排序算法的补充，本篇文章介绍两种冒泡算法的简单优化算法，即鸡尾酒排序和地精排序，废话不多说，进入正文．



鸡尾酒(Cocktail)排序算法



鸡尾酒排序，针对普通冒泡排序每次循环只能排定一个数的缺点，进行改进，其基本思想为，无序数组中，先找到最小的数字，把他放到第一位，然后找到最大的数字放到最后一位，完成一次循环；然后再找到第二小的数字放到第二位，再找到第二大的数字放到倒数第二位，完成第二次排序，以此类推，直到完成排序，由此可见在每次循环中可以排定两个数字，并且外层排序可以缩减到原来循环次数的一半，其代码如下：

public static void sort(int[] nums) {
    Arrays.nonBlank(nums);
    for (int i = 0; i < nums.length / 2; i++) {
        for (int j = i; j < nums.length - i - 1; j++) {
            if (nums[j] > nums[j + 1]) {
                swap(nums, j, j + 1);
            }
        }
        for (int j = nums.length - i - 1; j > i; j--) {
            if (nums[j] < nums[j - 1]) {
                swap(nums, j, j - 1);
            }
        }
    }
}

鸡尾酒排序的时间复杂度与冒泡排序相同，鸡尾酒排序等于是冒泡排序的轻微变形，不同的地方在于从低到高然后从高到低，而冒泡排序则仅从低到高去比较序列里的每个元素。



地精(Gnome)排序



地精排序，传说有一个地精在排列一排花盘。它从前至后的排列，如果相邻的两个花盘顺序正确，他向前一步；如果花盘顺序错误，他后退一步，直到所有的花盘的顺序都排列好。普通的冒泡排序是朝着一个方向走，而鸡尾酒排序是在整个数列上先往后走，再往前走；地精排序就是在数列的一部分上，如果有序就往前走，如果无序就往后退，然后让其有序，再往后走，是不是很像＂一步两步，一步两步，像魔鬼的步伐，像地精的步伐＂，其实质还是交换，其代码如下：

public static void gnomeSort(int[] nums) {
    Arrays.nonBlank(nums);
    int i = 1;
    while (i < nums.length) {
        if (i == 0 || nums[i] >= nums[i - 1]) i++;
        else {
            swap(nums, i, i - 1);
            i--;
        }
    }
}

比起冒泡排序，地精排序的有效代码行数只有５行，不得不说这个算法实现确实是很简单，但是要特别注意的一点是边界，如果没有i==0的条件的话，这个算法是不正确的，地精排序的时间复杂度也是O(n^2)，虽然时间上没有太大的提升，但是给了我们一种全新的思路．



总结



本片文章介绍了两种冒泡算法的变种，如果在面试的时候写出这样的冒泡排序，是不是有点让人眼前一亮的赶脚，其实这不是本片文章的重点，现在来划重点了，本片文章是学习两个重要单词，cocktail和gnome，计算机人基本都知道gnome，但我相信知道地精的一定不太多，go语言的土拨鼠是不是也受到了地精的影响呢？有待考证呀！本片文章结束．



别人为食而生存，我为生存而食　　泰勒斯