鸡尾酒排序

鸡尾酒排序算法是一种定向的冒泡排序算法，由于其来回折腾，因此又叫鸡尾酒搅拌排序、来回排序或者是涟漪排序、快乐小时排序。这个算法与冒泡排序的不同之处在于排序时是以双向在序列中进行排序的。

算法思想：

1. 采用冒泡排序的思路，第一躺沿正方向找到最大值；
2. 第二趟，从n-1个元素位置，沿反方向找到最小值
3. 第三趟，从第2个元素位置，沿正方向找到第二大的值，冒泡到n-1
4. 重复上面的操作，直到排序完成

代码实现

void cocktail_sort(int arr[], int len) {
    int i, left = 0, right = len;
    int temp;
    while (left < right) {
        for (i = left; i < right; i++)
            if (arr[i] > arr[i + 1]) {
                temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        right--;
        for (i = right; i > left; i--)
            if (arr[i - 1] > arr[i]) {
                temp = arr[i];
                arr[i] = arr[i - 1];
                arr[i - 1] = temp;
            }
        left++;
    }
}

算法分析

• 最优的情况下，复杂度为O(n)，当然，也是要引入标志位
• 最差的情况下，复杂度为O(n^2)，当然，会比冒泡排序算法性能好一点
• 平均复杂度为O(n^2)
• 相比于冒泡排序，不同的地方在于从低到高，然后从高到低，因此可以得到比冒泡排序稍微好一些的性能。

可以这么总结：相对于冒泡排序，采用鸡尾酒排序，性能至少不会变坏，大多数情况下能获得更好的性能。

过程举例

cocktail_sort_example.png

动态过程

Sorting_shaker_sort_anim.gif