盒子
盒子
文章目录
  1. 鸡尾酒排序(双向冒泡排序)

鸡尾酒排序

鸡尾酒排序(双向冒泡排序)

鸡尾酒排序,也叫定向冒泡排序,是冒泡排序的一种改进。
此算法与冒泡排序的不同处在于从低到高然后从高到低,而冒泡排序则仅从低到高去比较序列里的每个元素。他可以得到比冒泡排序稍微好一点的效能。

1
2
// 栗子
let arr = [45, 19, 77, 81, 13, 28, 18, 19, 77]

具体实现:

  1. 从左到右, 找到最大的数81, 放到数组末尾
  2. 从右到左, 找到剩余数组中最小的数, 放到数组开头
  3. 从左到右, 在剩余数组中找到最大数, 放在剩余数组的末尾

下面这个图, 更容易理解为什么叫鸡尾酒排序(是不是很像一个鸡尾酒杯子)

鸡尾酒排序图解

鸡尾酒排序的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
let shakerSort = array => {
let swap = (array, i, j) => { // 交换两个元素的值
let temp = array[i];
array[i] = array[j];
array[j] = temp;
};
let length = array.length,
left = 0, // 数组中第一个数的索引为0
right = length - 1,
lastSeappedLeft = left,
lastSwappedRight = right,
i,
j;
while( left < right ) { // 假如当前左边索引小于右边索引
// 从左到右
lastSwappedRight = 0;
for( i = left; i < right; i++) {
if(array[i] > array[i + 1]) {// 判断两个元素顺序是否正确
swap(array, i, i+1);
lastSwappedRight = i;
}
}
right = lastSwappedRight;
lastSeappedLeft = length -1; //
// 从右到左
for(j = right; left < j; j--) {
if(array[j - 1] > array[j]) {// 交换位置
swap(array, j - 1, j);
lastSeappedLeft = j;
}
}
left = lastSeappedLeft;
}
}

图解:

鸡尾酒排序