排序算法之：鸡尾酒排序（Cocktail Sort）的优化与边界条件处理

题目描述
鸡尾酒排序是冒泡排序的一种变体，通过双向交替扫描数组来优化冒泡排序的效率。在每一轮排序中，先从左到右将最大元素“冒泡”到右侧正确位置，再从右到左将最小元素“冒泡”到左侧正确位置。这种双向移动可以减少排序所需的轮数，尤其适用于部分已排序的数组。但算法仍需处理边界条件（如提前终止）和优化交换操作。本题要求实现鸡尾酒排序，并分析其优化策略与边界条件处理。

解题过程

1. 基础思想

• 鸡尾酒排序的核心是双向冒泡：
  • 奇数轮（从左到右）：比较相邻元素，若左大于右则交换，将当前最大元素移到右侧。
  • 偶数轮（从右到左）：比较相邻元素，若右小于左则交换，将当前最小元素移到左侧。
• 每完成一轮双向扫描，数组的未排序范围会从两端各缩小一个位置。

2. 基础算法实现

def cocktail_sort_basic(arr):
    n = len(arr)
    for i in range(n // 2):  # 只需n/2轮双向扫描
        # 从左到右冒泡（奇数轮）
        for j in range(i, n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
        # 从右到左冒泡（偶数轮）
        for j in range(n - 1 - i, i, -1):
            if arr[j] < arr[j - 1]:
                arr[j], arr[j - 1] = arr[j - 1], arr[j]

• 问题：未处理提前终止条件，即使数组已排序仍会完成所有轮次。

3. 优化1：提前终止机制

• 引入标志位 swapped，记录每轮扫描是否发生交换。若某一轮双向均无交换，说明数组已排序，可提前终止。

def cocktail_sort_optimized(arr):
    n = len(arr)
    left, right = 0, n - 1
    swapped = True
    
    while swapped:
        swapped = False
        # 从左到右扫描
        for i in range(left, right):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                swapped = True
        right -= 1  # 右侧边界左移
        
        if not swapped:
            break  # 若无交换则提前终止
        
        swapped = False
        # 从右到左扫描
        for i in range(right, left, -1):
            if arr[i] < arr[i - 1]:
                arr[i], arr[i - 1] = arr[i - 1], arr[i]
                swapped = True
        left += 1  # 左侧边界右移

4. 优化2：记录最后一次交换位置

• 进一步减少无效比较：记录每轮最后一次交换的位置，下一轮的扫描范围可缩小至该位置。

def cocktail_sort_advanced(arr):
    n = len(arr)
    left, right = 0, n - 1
    swapped = True
    
    while swapped:
        swapped = False
        last_swap = right
        # 从左到右扫描
        for i in range(left, right):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                swapped = True
                last_swap = i  # 记录最后一次交换的位置
        right = last_swap  # 缩小右边界
        
        if not swapped:
            break
        
        swapped = False
        last_swap = left
        # 从右到左扫描
        for i in range(right, left, -1):
            if arr[i] < arr[i - 1]:
                arr[i], arr[i - 1] = arr[i - 1], arr[i]
                swapped = True
                last_swap = i
        left = last_swap  # 缩小左边界

5. 边界条件处理

• 空数组或单元素数组：直接返回，无需排序。
• 已排序数组：通过 swapped 标志在第一轮扫描后提前终止。
• 逆序数组：需完成全部 n/2 轮扫描，但通过记录最后交换位置可减少比较次数。

6. 复杂度分析

• 时间复杂度：
  • 最好情况（已排序数组）：O(n)，仅一轮扫描后提前终止。
  • 最坏情况（完全逆序）：O(n²)，但比普通冒泡排序减少约一半的轮次。
• 空间复杂度：O(1)，原地排序。

7. 应用场景

• 适用于部分已排序的数组（如大部分元素有序，仅少数元素无序）。
• 在数据分布均匀且规模较小时，性能优于普通冒泡排序。