鸡尾酒排序（Cocktail Sort）
鸡尾酒排序（Cocktail Sort），又称为双向冒泡排序（Bidirectional Bubble Sort）或鸡尾酒搅拌排序，是冒泡排序的一种变种。它双向扫描，一轮里既把较大的元素“沉”到数组右端，也把较小的元素“浮”到左端，比单向冒泡少走几轮。
1. 鸡尾酒排序的基本概念
鸡尾酒排序的核心思想是：
- 双向扫描: 先从左到右扫一遍，再从右到左扫一遍，一轮里同时处理大值和小值，减少扫描的轮数。
- 相邻交换: 每次扫描都靠交换相邻的两个元素，把未排序的部分逐步理顺。
2. 鸡尾酒排序的算法步骤
初始化: 设置两个指针，
left和right，分别指向数组的开始和结束。前向扫描（从左到右）:
- 从左到右扫描数组，将较大的元素移动到数组的右边（即末尾）。
- 在每次交换时，更新右指针的位置，因为已经有序的部分不再需要参与排序。
后向扫描（从右到左）:
- 从右到左扫描数组，将较小的元素移动到数组的左边（即开头）。
- 在每次交换时，更新左指针的位置，因为已经有序的部分不再需要参与排序。
重复过程: 不断重复前向扫描和后向扫描，直到整个数组有序。
3. 鸡尾酒排序的时间复杂度和空间复杂度
时间复杂度:
- 最坏情况: $O(n^2)$，与冒泡排序相同。
- 最佳情况: $O(n)$，如果数组已经有序，则只需一次前向和后向扫描。
- 平均情况: $O(n^2)$，由于需要双向扫描，平均性能与冒泡排序类似。
空间复杂度: $O(1)$，鸡尾酒排序是原地排序算法，不需要额外的存储空间。
4. 鸡尾酒排序的代码示例
go
package main
import "fmt"
// 鸡尾酒排序
func cocktailSort(arr []int) {
n := len(arr)
if n <= 1 {
return
}
// 初始化指针
left, right := 0, n-1
for left < right {
// 前向扫描
swapped := false
for i := left; i < right; i++ {
if arr[i] > arr[i+1] {
arr[i], arr[i+1] = arr[i+1], arr[i]
swapped = true
}
}
right--
// 如果没有交换，说明数组已经有序
if !swapped {
break
}
// 后向扫描
swapped = false
for i := right; i > left; i-- {
if arr[i] < arr[i-1] {
arr[i], arr[i-1] = arr[i-1], arr[i]
swapped = true
}
}
left++
}
}
func main() {
arr := []int{5, 1, 4, 2, 8, 6, 3, 7}
fmt.Println("Original array:", arr)
cocktailSort(arr)
fmt.Println("Sorted array:", arr)
}5. 鸡尾酒排序的优缺点
和单向冒泡比，鸡尾酒排序一轮里两头都排，部分有序的数据能少扫几轮，代价是要维护前后两个方向的扫描，实现比冒泡排序复杂。它最坏情况仍是 $O(n^2)$，大规模数据用它不划算。
总结
鸡尾酒排序是双向的冒泡排序：一轮从左到右把大值沉下去，再从右到左把小值浮上来。已有序的数组一次前后扫描就能确认，复杂度 $O(n)$；排不好的数据仍是 $O(n^2)$，与冒泡排序打平。