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

题目描述：
Cocktail Shaker Sort（鸡尾酒摇动排序）是冒泡排序的一种变体，它通过双向遍历数组来改善性能。算法从左到右遍历时将最大元素"冒泡"到右侧，然后从右到左遍历时将最小元素"冒泡"到左侧，如此往复直到数组完全有序。题目要求实现这个算法，并解决边界条件处理问题，同时进行性能优化。

解题过程：

1. 基础算法原理
   鸡尾酒排序的核心思想是双向冒泡。与普通冒泡排序只从左到右遍历不同，它交替进行两个方向的遍历：

• 正向遍历：将当前未排序部分的最大元素移动到最右端
• 反向遍历：将当前未排序部分的最小元素移动到最左端

2. 基础实现步骤

def cocktail_shaker_sort_basic(arr):
    n = len(arr)
    left = 0
    right = n - 1
    
    while left < right:
        # 正向遍历：将最大元素移到右边
        for i in range(left, right):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
        right -= 1  # 右边界左移
        
        # 反向遍历：将最小元素移到左边
        for i in range(right, left, -1):
            if arr[i - 1] > arr[i]:
                arr[i - 1], arr[i] = arr[i], arr[i - 1]
        left += 1  # 左边界右移
    
    return arr

3. 第一次优化：提前终止
   当在一次完整的双向遍历中没有发生任何交换时，说明数组已经有序，可以提前终止：

def cocktail_shaker_sort_optimized(arr):
    n = len(arr)
    left = 0
    right = n - 1
    swapped = True
    
    while swapped and left < right:
        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 - 1] > arr[i]:
                arr[i - 1], arr[i] = arr[i], arr[i - 1]
                swapped = True
        left += 1
    
    return arr

4. 边界条件处理的关键问题
   在基础实现中，我们需要特别注意几个边界条件：

• 当数组长度为0或1时的处理
• 遍历范围的精确控制
• 在反向遍历时，确保不会访问负索引

5. 进阶优化：记录最后交换位置
   通过记录最后一次交换的位置，可以进一步缩小每次遍历的范围：

def cocktail_shaker_sort_advanced(arr):
    n = len(arr)
    if n <= 1:
        return arr
        
    left = 0
    right = n - 1
    last_swap = 0
    
    while left < right:
        # 正向遍历
        last_swap = left
        for i in range(left, right):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                last_swap = i
        right = last_swap  # 更新右边界到最后一次交换的位置
        
        # 如果右边界已经与左边界相遇，提前终止
        if left >= right:
            break
            
        # 反向遍历
        last_swap = right
        for i in range(right, left, -1):
            if arr[i - 1] > arr[i]:
                arr[i - 1], arr[i] = arr[i], arr[i - 1]
                last_swap = i
        left = last_swap  # 更新左边界到最后一次交换的位置
    
    return arr

6. 性能分析

• 时间复杂度：
  • 最好情况：O(n) - 当数组已经有序时
  • 平均情况：O(n²)
  • 最坏情况：O(n²) - 当数组完全逆序时
• 空间复杂度：O(1) - 原地排序
• 稳定性：稳定排序算法

7. 实际应用场景
   鸡尾酒排序在以下场景中表现较好：

• 大部分元素已经基本有序的数组
• 需要稳定排序且空间有限的场景
• 小规模数据的排序

8. 完整测试用例

# 测试各种边界情况
test_cases = [
    [],                    # 空数组
    [1],                   # 单元素
    [1, 2, 3, 4, 5],       # 已排序
    [5, 4, 3, 2, 1],       # 逆序
    [3, 1, 4, 1, 5, 9, 2, 6],  # 随机数组
    [5, 5, 5, 5],          # 全相同元素
]

for i, test_case in enumerate(test_cases):
    result = cocktail_shaker_sort_advanced(test_case.copy())
    print(f"测试用例 {i+1}: {test_case} -> {result}")

通过这种循序渐进的优化过程，我们得到了一个既高效又健壮的鸡尾酒排序实现，能够正确处理各种边界情况，并在最佳情况下达到线性时间复杂度。