鸡尾酒排序
鸡尾酒排序前言
笔者最近看算法文章的时候，看到一个鸡尾酒排序的算法，是冒泡排序的一种变种。记录一下，每天一个知识点。
算法概述
鸡尾酒排序（Cocktail Sort），又称双向冒泡排序（Bidirectional Bubble Sort）、摇摆排序（Shake Sort），是对传统冒泡排序的一种改进。它在基本思想上与冒泡排序类似，但排序过程是交替地从左到右和从右到左进行的，从而可以更快地将元素移动到正确的位置。
核心思想
[*]类似于冒泡排序，通过比较相邻元素并交换顺序错误的对。
[*]不同之处在于：
[*]第一轮：从左向右遍历，把最大的元素“冒泡”到末尾。
[*]第二轮：从右向左遍历，把最小的元素“沉降”到开头。
[*]如此反复，每次缩小未排序部分的范围，直到整个数组有序。
特点
特性描述时间复杂度最坏 O($n{2}$)，平均O($n$)，最好 O($n$)（已有序）空间复杂度O(1)，原地排序稳定性✅ 稳定排序（相等元素顺序不变）是否比较排序✅ 是javascript 实现示例
var arr =;
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 <= arr) continue;
swap(arr, i, i + 1);
isSorted = false;
}
// 如果已经有序，则结束
if(isSorted) break;
isSorted = true;
// 第二轮：从右到左进行，小数移动到左侧
for (var i = end - 1; i > start; i--){
if (arr >= arr) continue;
swap(arr, i, i - 1);
isSorted = false;
}
start++;
end--;
}
return arr;
}
// ---------辅助函数-----------
function swap(arr, i, j) {
var temp = arr;
arr = arr;
arr = temp;
}
function clone(arr) {
return arr.slice(0);
}示例说明
以数组 为例：
[*]第一轮从左到右：将最大值 8 移动到最右边。
[*]第二轮从右到左：将最小值 0 移动到最左边。
[*]依此类推，每轮缩小排序区间，直到全部有序。
优点 & 缺点
优点缺点比普通冒泡排序快一些（尤其在两端有极值时）时间复杂度仍为 O(n^2)，不适合大数据集实现简单、稳定效率远低于快速排序、归并排序等高级算法使用场景
[*]数据量较小的教学场景。
[*]当数据已经接近有序时效率较高。
[*]用于演示排序算法中的“优化思想”。
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]