鸡尾酒排序

何书艺 · 2025-6-28 12:48:40

鸡尾酒排序

前言

笔者最近看算法文章的时候，看到一个鸡尾酒排序的算法，是冒泡排序的一种变种。记录一下，每天一个知识点。
算法概述

鸡尾酒排序（Cocktail Sort），又称双向冒泡排序（Bidirectional Bubble Sort）、摇摆排序（Shake Sort），是对传统冒泡排序的一种改进。它在基本思想上与冒泡排序类似，但排序过程是交替地从左到右和从右到左进行的，从而可以更快地将元素移动到正确的位置。
核心思想

类似于冒泡排序，通过比较相邻元素并交换顺序错误的对。
不同之处在于：
- 第一轮：从左向右遍历，把最大的元素“冒泡”到末尾。
- 第二轮：从右向左遍历，把最小的元素“沉降”到开头。
- 如此反复，每次缩小未排序部分的范围，直到整个数组有序。

特点

特性描述时间复杂度最坏 O($n{2}$)，平均O($n$)，最好 O($n$)（已有序）空间复杂度O(1)，原地排序稳定性✅ 稳定排序（相等元素顺序不变）是否比较排序✅ 是javascript 实现示例

var arr =[5, 1, 4, 2, 8, 0, 3];
var sortedArr = cocktailSort(clone(arr));
console.log(arr,sortedArr);
function cocktailSort(arr) {
var len = arr.length;
var start = 0;
var end = len - 1;
var isSorted = false;
while (isSorted === false) {
isSorted = true;
// 第一轮：从左到右进行，大数移动到右侧
for (var i = start; i < end; i++) {
if (arr[i] <= arr[i + 1]) continue;
swap(arr, i, i + 1);
isSorted = false;
}
// 如果已经有序，则结束
if(isSorted) break;
isSorted = true;
// 第二轮：从右到左进行，小数移动到左侧
for (var i = end - 1; i > start; i--){
if (arr[i] >= arr[i - 1]) continue;
swap(arr, i, i - 1);
isSorted = false;
}
start++;
end--;
}
return arr;
}
// ---------辅助函数-----------
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function clone(arr) {
return arr.slice(0);
}

复制代码

示例说明

以数组 [5, 1, 4, 2, 8, 0, 3] 为例：

第一轮从左到右：将最大值 8 移动到最右边。
第二轮从右到左：将最小值 0 移动到最左边。
依此类推，每轮缩小排序区间，直到全部有序。

优点 & 缺点

优点缺点比普通冒泡排序快一些（尤其在两端有极值时）时间复杂度仍为 O(n^2)，不适合大数据集实现简单、稳定效率远低于快速排序、归并排序等高级算法使用场景

数据量较小的教学场景。
当数据已经接近有序时效率较高。
用于演示排序算法中的“优化思想”。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

账号		自动登录	找回密码
密码			立即注册