鸡尾酒排序

【基本思想】

鸡尾酒排序也称双向冒泡排序、定向冒泡排序，是原始冒泡排序的改进

双向冒泡排序与冒泡排序的不同在于其从低到高比较，然后再从高到低比较，如此循环往复，直到序列有序，而冒泡排序仅是从低到高的去比较序列中的每个元素

其实现借助两个指针来完成，一个作为头指针，负责从前向后扫描，一个作为尾指针，负责从后向前扫描，外层循环依靠指针控制数组左右边界，内层循环分别控制前后边界的排序

鸡尾酒排序的宏观排序过程如下图

【实例】

以数列 $\{6,5,3,1,8,7,2,4\}$ 为例，演示双向冒泡排序过程：

可以发现，在第 $5$ 趟时，未发生交换，此时数列已经有序

与原始冒泡排序相比，有了一定的优化

【性能分析】

鸡尾酒排序适用于顺序存储、链式存储结构，当 $i>j$，且 $a[i]=a[j]$ 时，不会发生交换，因此其是一种稳定排序算法

鸡尾酒排序仅需常数个辅助空间，作为待插入记录的暂存单元，因此其空间复杂度为：

$$O(1)$$

鸡尾酒排序虽相较冒泡排序相比有了优化，但在数据量较少时优势并不明显，在较大数据量时相较原始冒泡排序有较大优势，其时间复杂度与冒泡排序相同，即：

$$O(n^2)$$

【实现】

朴素实现

void cocktailSort (int a[], int n) {
    int left = 1, right = n;
    while (left < right) {
        /*前半轮,将最大元素放到后面*/
        for (int i = left; i < right; i++)
            if(a[i] > a[i+1])
                swap(a[i], a[i+1]);
        right--;
        /*后半轮,将最小元素放到前面*/
        for (int i = right; i > left; i--)
            if(a[i-1] > a[i])
                swap(a[i], a[i-1]);
        left++;
    }
}

判断优化

void cocktailSort (int a[], int n) {
    int left = 1, right = n;
    while (left < right) {
        bool flag = false; //判断是否有交换
        /*前半轮,将最大元素放到后面*/
        for (int i = left; i < right; i++) {
            if(a[i] > a[i+1]) {
                swap(a[i], a[i+1]);
                flag = true;  //有交换说明仍需排序
            }
        }
        right--;
        if (!flag)  //若本趟无交换，说明表已经有序，终止
            break;
        
        /*后半轮,将最小元素放到前面*/
        for (int i = right; i > left; i--) {
            if(a[i-1] > a[i]) {
                swap(a[i], a[i-1]);
                flag = true;  //有交换说明仍需排序
            }
        }
        left++;
        if (!flag)  //若本趟无交换，说明表已经有序，终止
            break;
    }
}