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

题目描述：
鸡尾酒摇动排序是冒泡排序的一种变体，它通过双向遍历数组来改善冒泡排序的性能。算法从左到右遍历时将最大元素"冒泡"到右侧正确位置，然后从右到左遍历时将最小元素"冒泡"到左侧正确位置，如此往复直到数组完全有序。

解题过程：

1. 基本算法框架
   鸡尾酒排序的核心思想是在每个完整的循环中执行两次遍历：

• 正向遍历：比较相邻元素，如果左 > 右则交换，将最大值移到右端
• 反向遍历：比较相邻元素，如果左 > 右则交换，将最小值移到左端

2. 基础实现步骤

def cocktail_shaker_sort(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
        
        if not swapped:
            break
            
        right -= 1
        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. 第二次优化：记录最后交换位置
   记录每次遍历中最后发生交换的位置，可以缩小遍历范围：

def cocktail_shaker_sort_advanced(arr):
    n = len(arr)
    left = 0
    right = n - 1
    
    while left < right:
        new_right = left
        # 正向遍历
        for i in range(left, right):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                new_right = i  # 记录最后交换位置
        
        right = new_right  # 更新右边界
        if left >= right:
            break
            
        new_left = right
        # 反向遍历
        for i in range(right, left, -1):
            if arr[i - 1] > arr[i]:
                arr[i - 1], arr[i] = arr[i], arr[i - 1]
                new_left = i  # 记录最后交换位置
        
        left = new_left  # 更新左边界
    
    return arr

5. 边界条件处理
   考虑特殊情况：

• 空数组或单元素数组：直接返回
• 已排序数组：通过提前终止优化处理
• 逆序数组：需要完整执行所有遍历

完整优化版本：

def cocktail_shaker_sort_final(arr):
    if len(arr) <= 1:
        return arr
        
    left = 0
    right = len(arr) - 1
    
    while left < right:
        # 正向遍历
        new_right = left
        for i in range(left, right):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                new_right = i
        
        right = new_right
        if left >= right:
            break
            
        # 反向遍历  
        new_left = right
        for i in range(right, left, -1):
            if arr[i - 1] > arr[i]:
                arr[i - 1], arr[i] = arr[i], arr[i - 1]
                new_left = i
        
        left = new_left
    
    return arr

6. 性能分析

• 时间复杂度：
  • 最好情况（已排序）：O(n)
  • 平均情况：O(n²)
  • 最坏情况（逆序）：O(n²)
• 空间复杂度：O(1)，原地排序
• 稳定性：稳定排序算法

这种双向遍历的策略使得鸡尾酒排序在处理某些特定数据分布时比普通冒泡排序有更好的性能表现。