好的，我注意到已讲过的题目列表中包含了许多经典和冷门的排序算法及其变种，但还没有专门讲解过 “Cocktail Sort” 的递归版本。这是一个有趣且能加深对算法理解的问题。让我们开始吧。

题目描述

用递归方式实现鸡尾酒排序（Cocktail Shaker Sort）

鸡尾酒排序（双向冒泡排序）是一种稳定的、基于比较的排序算法。它是冒泡排序的一种改进：

1. 每一趟排序分为两个方向：从左到右，将最大元素“冒泡”到末尾；接着从右到左，将最小元素“冒泡”到开头。
2. 这样就避免了传统冒泡排序中，小元素在末尾时只能极其缓慢地向一端移动的问题。

递归的核心思想是：排序过程可以看作在一段不断缩小的子数组上，重复进行“双向冒泡”的操作。

解题过程详解

我们可以将递归的“鸡尾酒排序”分解为两个清晰的层次：

• 外层递归（CocktailSortRecursive）：负责控制排序的“范围”（即子数组的左右边界）。每次递归调用处理更小的子数组。
• 内层递归（BubblePass）：负责在一个方向上（从左到右或从右到左）完成一趟冒泡，即单方向的比较和交换。它也可以是递归实现的，或者用循环。这里我们为了概念清晰，先用递归实现单向冒泡。

步骤 1：定义问题的递归结构

对于一个待排序的数组 arr，我们从索引 left 到 right 进行排序。

1. 基线条件（Base Case）：如果 left >= right，说明子数组已经为空或只有一个元素，自然有序，无需再排序。
2. 递归条件（Recursive Case）：
   a. 正向冒泡（左到右）：遍历 arr[left] 到 arr[right-1]，如果 arr[i] > arr[i+1] 就交换。这样一趟结束后，arr[right] 存放的是该子数组中的最大元素，且已处于最终正确位置。
   b. 反向冒泡（右到左）：遍历 arr[right-1] 到 arr[left]，如果 arr[i] < arr[i-1] 就交换。这样一趟结束后，arr[left] 存放的是该子数组中的最小元素，且已处于最终正确位置。
   c. 缩小范围：现在，最大元素和最小元素都已归位。我们接下来只需要对缩小的子数组 arr[left+1] 到 arr[right-1] 进行排序。

这个“缩小范围”的动作，就是外层递归调用自身。

步骤 2：实现单向冒泡的递归函数（辅助函数）

我们先实现一个辅助函数 bubblePass，它在给定的方向（forward = true 表示从左到右，false 表示从右到左）上，对 arr[left:right] 的范围进行一次冒泡，并将一个最值移动到边界。

def bubblePass(arr, start, end, step, swapped):
    """
    递归地执行单向冒泡。
    :param arr: 待排序数组
    :param start: 当前遍历的起始索引（包含）
    :param end: 当前遍历的结束索引（包含）
    :param step: 步长，+1 表示正向，-1 表示反向
    :param swapped: 记录本轮是否发生过交换（引用传递，通常用列表或字典包装）
    """
    # 基线条件：当遍历范围无效或只剩一个元素时，停止
    if (step > 0 and start >= end) or (step < 0 and start <= end):
        return

    # 比较当前元素和它的“下一个”元素（由step决定方向）
    next_idx = start + step
    if (step > 0 and arr[start] > arr[next_idx]) or (step < 0 and arr[start] < arr[next_idx]):
        # 交换元素
        arr[start], arr[next_idx] = arr[next_idx], arr[start]
        swapped[0] = True  # 标记发生了交换

    # 递归处理下一个位置
    bubblePass(arr, next_idx, end, step, swapped)

步骤 3：实现主递归函数

现在，我们来实现外层的主递归函数 cocktailSortRecursive。

def cocktailSortRecursive(arr, left, right):
    """
    递归地执行鸡尾酒排序。
    :param arr: 待排序数组
    :param left: 当前子数组的左边界（包含）
    :param right: 当前子数组的右边界（包含）
    """
    # 基线条件：子数组无需排序
    if left >= right:
        return

    swapped = [False]  # 用于标记本轮是否发生交换，优化提前终止

    # 第一步：正向冒泡（左 -> 右），将最大值移到 right
    bubblePass(arr, left, right, 1, swapped)

    # 如果正向冒泡没发生任何交换，且 left < right，说明数组已经有序，可以提前终止。
    # 但为了保险，我们继续反向冒泡的逻辑，但在反向冒泡中也会检测。
    # 更优的提前终止逻辑在步骤4讨论。

    # 第二步：反向冒泡（右 -> left+1，注意左边界已经有一个最小值就位，所以从 right-1 开始）
    bubblePass(arr, right - 1, left, -1, swapped)

    # 如果本轮没有任何交换发生，说明数组已经有序，无需继续递归
    if not swapped[0]:
        return

    # 第三步：递归地对中间未排序的子数组排序（左右边界各收缩1）
    cocktailSortRecursive(arr, left + 1, right - 1)

步骤 4：优化与边界处理

上面的实现是正确的，但可以优化，并且需要仔细理解边界。

1. 提前终止的优化：我们可以在外层递归中加入一个变量来记录“本轮是否发生交换”。如果一趟正向和一趟反向都没有发生任何交换，那么整个子数组已经有序，可以立即返回，而不进行下一次递归。
   • 在上面的代码中，我们用 swapped 变量记录了这一点。
2. 边界索引的处理：这是最需要细致的地方。
   • bubblePass 的 end 参数是包含的。正向冒泡时，我们比较 arr[i] 和 arr[i+1]，所以 i 应该从 left 遍历到 right-1，因此调用 bubblePass(arr, left, right-1, 1, swapped)。但我们的 bubblePass 函数设计是 start 到 end（包含）进行遍历比较 arr[start] 和 arr[start+step]。为了保证 start+step 不越界，我们需要让 end 正好等于最后一个需要比较的元素的索引。
   • 反向冒泡时，我们比较 arr[i] 和 arr[i-1]，i 应该从 right 遍历到 left+1，因此调用 bubblePass(arr, right, left+1, -1, swapped)。注意方向是 -1，起始是 right，结束是 left+1。

修正后的主函数（带精确边界）

def cocktailSortRecursive(arr, left, right):
    """
    递归地执行鸡尾酒排序（精确边界版）。
    """
    # 基线条件
    if left >= right:
        return

    swapped = [False]

    # 正向冒泡：遍历 [left, right-1]，比较 arr[i] 和 arr[i+1]
    # bubblePass 会处理从 start=left 到 end=right-1 的每个i，比较 arr[i] 和 arr[i+1]
    bubblePass(arr, left, right - 1, 1, swapped)

    # 反向冒泡：遍历 [right, left+1]（反向），比较 arr[i] 和 arr[i-1]
    # bubblePass 会处理从 start=right 到 end=left+1 的每个i，比较 arr[i] 和 arr[i-1]
    # 因为 step=-1，所以是 i 从 right 递减到 left+1
    bubblePass(arr, right, left + 1, -1, swapped)

    # 提前终止优化
    if not swapped[0]:
        return

    # 递归处理缩小的子数组
    cocktailSortRecursive(arr, left + 1, right - 1)

# 对外的封装函数
def cocktailSort(arr):
    if len(arr) <= 1:
        return arr
    cocktailSortRecursive(arr, 0, len(arr) - 1)
    return arr

# 测试
if __name__ == "__main__":
    test_array = [5, 1, 4, 2, 8, 0, 2]
    print("原始数组:", test_array)
    sorted_array = cocktailSort(test_array)
    print("排序后数组:", sorted_array)
    # 输出：原始数组: [5, 1, 4, 2, 8, 0, 2]
    #       排序后数组: [0, 1, 2, 2, 4, 5, 8]

步骤 5：时间与空间复杂度分析

• 时间复杂度：
  • 最坏和平均情况：仍然是 O(n^2)，其中 n 是数组长度。因为递归深度为 O(n)（每次左右边界各缩进1），而每层递归中 bubblePass 的时间复杂度是 O(当前子数组长度)，总和仍是平方级。
  • 最好情况（数组已有序）：优化后的版本（有 swapped 检测）只需进行一趟正向和一趟反向扫描，时间复杂度为 O(n)。
• 空间复杂度：
  • 主要来自递归调用栈。在最坏情况下，递归深度约为 n/2，因此空间复杂度为 O(n)。这不如迭代版本（空间复杂度 O(1)），这是递归实现鸡尾酒排序的一个缺点。

总结

通过递归实现鸡尾酒排序，我们：

1. 清晰地分解了问题：将“对整个数组排序”分解为“先双向冒泡一趟，再对中间更小的子数组递归排序”。
2. 深入理解了递归与迭代的对应关系：递归的“缩小范围”对应着迭代中 while 循环的 left++ 和 right--。
3. 实践了递归的基线条件和递归条件。
4. 体会了优化：通过 swapped 标志，我们可以在最好情况下提前终止。
5. 分析了优缺点：递归实现逻辑清晰，易于理解递归思想，但产生了 O(n) 的栈空间开销，不如迭代版本节省空间。在实际工程中，对于鸡尾酒排序这类简单算法，通常更推荐迭代实现。