鸡尾酒排序 Cocktail Shaker Sort
交换排序 · 双向冒泡 · 专治「乌龟」
冒泡的乌龟问题
冒泡排序每趟从左往右扫，大元素（兔子）一趟就能蹦到右端；可待在尾部的小元素（乌龟）每趟只能往左挪 一格——数组 [..., 1] 里的 1 要爬 n-1 趟才能回家。方向不对称，是单向扫描的天生短板。
来回摇：双向冒泡
鸡尾酒排序像调酒一样来回摇：先一趟从左到右把最大的冒到右端（右边界 right--），再一趟从右到左把最小的沉到左端（左边界 left++）——活动区 [left, right] 两端向中间收缩，乌龟也能一趟直达。任何一趟零交换，说明区间已有序，直接提前收工。
下面固定 8 个数 [4, 2, 6, 3, 8, 5, 7, 1]——尾部藏了只乌龟 1。点「下一步」：第 1 趟（→）把 8 冒到右端、右端变绿；第 2 趟（←）六连交换把乌龟 1 一趟送回头、左端也变绿——两端绿色逐渐夹住中间乱序区；第 4 趟（←）全程不交换，提前收工。
第 1 趟（→）：从左到右，把最大的冒到右端
1function cocktailSort(a: number[]): number[] {
2 let left = 0, right = a.length - 1;
3 while (left < right) {
4 let swapped = false;
5 for (let j = left; j < right; j++) {
6 if (a[j] > a[j + 1]) {
7 [a[j], a[j + 1]] = [a[j + 1], a[j]];
8 swapped = true;
9 }
10 }
11 right--;
12 if (!swapped) break;
13 swapped = false;
14 for (let j = right; j > left; j--) {
15 if (a[j - 1] > a[j]) {
16 [a[j - 1], a[j]] = [a[j], a[j - 1]];
17 swapped = true;
18 }
19 }
20 left++;
21 if (!swapped) break;
22 }
23 return a;
24}
n8
left0
right7
方向→
j0
左/右值4 / 2
swappedInPassfalse
swapCount0
1 / 49
复杂度：还是 O(n²)，但趟数省了
最坏与平均仍是 O(n²)、原地、稳定——它不改变冒泡的量级，改善的是趟数：乌龟场景里单向冒泡要 n-1 趟，双向来回一次就解决；对「基本有序、少数元素错位」的数据配合提前收工非常利落。它是「调整扫描方向」这个小改动带来大改善的经典教学案例。
冒泡排序：单向扫，兔子快、乌龟慢——尾部小元素每趟只挪一格。
鸡尾酒排序（本页）：来回扫 + 两端收缩，乌龟一趟到家；任一趟零交换提前收工。
两者同为 O(n²) 稳定原地排序，差别全在扫描方向的对称性。
鸡尾酒排序（本页）：来回扫 + 两端收缩，乌龟一趟到家；任一趟零交换提前收工。
两者同为 O(n²) 稳定原地排序，差别全在扫描方向的对称性。
对照冒泡排序页把同一套 compare/swap 再走一遍，你会发现本页唯一的新东西就是「掉头」——有时候，算法优化就这么朴素。