排序算法之：鸡尾酒排序（Cocktail Sort） 题目描述 鸡尾酒排序，也称为双向冒泡排序或涟漪排序，是冒泡排序的一种变体。与冒泡排序只从左到右遍历不同，鸡尾酒排序在每一轮排序中会先从左到右遍历，将最大的元素移动到右侧正确位置，接着从右到左遍历，将最小的元素移动到左侧正确位置。这样交替进行，可以减少排序所需的轮数，尤其适用于大部分元素已有序的数组。 给定一个整数数组 [5, 1, 4, 2, 8, 0, 2] ，请使用鸡尾酒排序算法对其进行升序排序，并详细解释每一步的过程。 解题过程 初始化与遍历方向控制 定义左右边界： left = 0 （数组起始索引）， right = n-1 （数组末尾索引，n为数组长度）。 设置一个标志位 swapped 用于检测单轮遍历中是否发生元素交换。 第一轮：从左到右遍历（正向冒泡） 遍历区间 [left, right) ，即索引 0 到 5（当前数组： [5, 1, 4, 2, 8, 0, 2] ）。 比较相邻元素，若左侧大于右侧则交换： 比较 5 和 1 → 交换 → [1, 5, 4, 2, 8, 0, 2] （ swapped = true ）。 比较 5 和 4 → 交换 → [1, 4, 5, 2, 8, 0, 2] 。 比较 5 和 2 → 交换 → [1, 4, 2, 5, 8, 0, 2] 。 比较 5 和 8 → 不交换。 比较 8 和 0 → 交换 → [1, 4, 2, 5, 0, 8, 2] 。 本轮将最大值 8 移到右侧，右边界收缩： right = 5 。 第一轮：从右到左遍历（反向冒泡） 遍历区间 [right, left) ，即索引 5 到 0（反向比较）。 比较相邻元素，若左侧大于右侧则交换（注意方向）： 比较 0 和 5 （索引4和3）→ 交换 → [1, 4, 2, 0, 5, 8, 2] 。 比较 0 和 2 （索引3和2）→ 交换 → [1, 4, 0, 2, 5, 8, 2] 。 比较 0 和 4 （索引2和1）→ 交换 → [1, 0, 4, 2, 5, 8, 2] 。 比较 0 和 1 （索引1和0）→ 交换 → [0, 1, 4, 2, 5, 8, 2] 。 本轮将最小值 0 移到左侧，左边界扩张： left = 1 。 第二轮：从左到右遍历 当前数组： [0, 1, 4, 2, 5, 8, 2] ，遍历区间 [left, right) = [1, 5) 。 比较交换： 比较 1 和 4 → 不交换。 比较 4 和 2 → 交换 → [0, 1, 2, 4, 5, 8, 2] 。 比较 4 和 5 → 不交换。 比较 5 和 8 → 不交换。 右边界收缩： right = 4 。 第二轮：从右到左遍历 遍历区间 [right, left) = [4, 1) （反向）。 比较交换： 比较 2 和 4 （索引2和3）→ 不交换（已有序）。 比较 2 和 1 （索引1和2）→ 不交换。 左边界扩张： left = 2 。 第三轮：从左到右遍历 当前数组： [0, 1, 2, 4, 5, 8, 2] ，遍历 [2, 4) 。 比较 2 和 4 、 4 和 5 均不交换，但末尾 8 和 2 未参与比较（因右边界限制）。 右边界收缩： right = 3 。 第三轮：从右到左遍历 遍历 [3, 2) ，无需比较（区间为空）。 此时 left = 2 与 right = 3 重叠，循环终止。 最终结果 数组未完全有序（ [0, 1, 2, 4, 5, 8, 2] ），因算法提前终止。需修正：在每轮遍历后检查 swapped 标志，若未发生交换则提前结束排序。本例中第二轮反向遍历后 swapped 为 false，应终止。 修正后的正确步骤 在第二轮反向遍历后，因无交换操作，直接结束排序，最终结果为 [0, 1, 2, 4, 5, 8, 2] 仍无序？ 关键修正 ：需在每轮双向遍历后检查 swapped ，若为 false 才终止。但本例中第二轮正向遍历有交换（ 4 和 2 ），因此继续。第三轮正向遍历无交换，反向遍历也无交换，最终终止。 实际正确流程 ：第三轮正向遍历后，数组为 [0, 1, 2, 4, 5, 2, 8] （将 2 移到 8 前），反向遍历调整后得到有序数组 [0, 1, 2, 2, 4, 5, 8] 。 总结 鸡尾酒排序通过双向遍历减少轮数，最优情况（数组已有序）时间复杂度为 O(n)，平均和最坏仍为 O(n²)。适用于部分有序的小规模数据。