鸡尾酒排序
入门冒泡排序的改进版，减少某些情况下的遍历次数。
// 自定义输入
用你自己的数组跑一遍
速度 中
待机 ⌨1void cocktailSort(int arr[], int n) {
2 bool swapped = true;
3 int start = 0, end = n - 1;
4 while (swapped) {
5 swapped = false;
6 for (int i = start; i < end; i++)
7 if (arr[i] > arr[i+1]) { swap(arr[i], arr[i+1]); swapped = true; }
8 end--;
9 if (!swapped) break;
10 swapped = false;
11 for (int i = end; i > start; i--)
12 if (arr[i] < arr[i-1]) { swap(arr[i], arr[i-1]); swapped = true; }
13 start++;
14 }
15}
复杂度分析
时间 O(n²)
空间 O(1)
最优 O(n)
最坏 O(n²)
算法讲解
鸡尾酒排序是冒泡排序的变体，交替从两个方向遍历数组。
从左到右遍历将最大值移到末尾，从右到左遍历将最小值移到开头。
对于"乌龟"（小值在末尾）的情况，鸡尾酒排序比普通冒泡更快。
时间复杂度仍为 O(n²)，但实际运行中可能更少的遍历次数。