79 lines
2.4 KiB
JavaScript
79 lines
2.4 KiB
JavaScript
import { swap } from '../util/index.mjs';
|
||
|
||
export function bubbleSort(arr) {
|
||
const n = arr.length;
|
||
for (let i = 1; i < n; i++) {
|
||
// 理解为何i从1开始，因为冒泡排序是两两比较的，此循环只是限制比较的次数
|
||
for (let j = 0; j < n - i; j++) {
|
||
// 此循环才是排序的关键，当当前值大于后一个值时交换位置，没做完一遍最后一个值永远是本轮循环最大的
|
||
if (arr[j] > arr[j + 1]) {
|
||
swap(arr, j, j + 1);
|
||
}
|
||
}
|
||
}
|
||
}
|
||
|
||
// 优化方案1
|
||
export function bubbleSort2(arr) {
|
||
const n = arr.length;
|
||
for (let i = 1; i < n; i++) {
|
||
let hasSort = true; // 添加标志位，默认是有序的，在一轮比较下来如果没有发生交换，说明整个数组就是有序的，直接结束排序
|
||
for (let j = 0; j < n - i; j++) {
|
||
if (arr[j] > arr[j + 1]) {
|
||
swap(arr, j, j + 1);
|
||
hasSort = false; // 交换元素之后，设置标志位为无序状态
|
||
}
|
||
}
|
||
if (hasSort === true) {
|
||
break;
|
||
}
|
||
}
|
||
}
|
||
|
||
// 优化方案2
|
||
export function bubbleSort3(arr) {
|
||
const n = arr.length;
|
||
let k = n - 1;
|
||
let swapPos = 0;
|
||
for (let i = 1; i < n; i++) {
|
||
let hasSort = true; // 添加标志位，默认是有序的，在一轮比较下来如果没有发生交换，说明整个数组就是有序的，直接结束排序
|
||
for (let j = 0; j < k; j++) {
|
||
if (arr[j] > arr[j + 1]) {
|
||
swap(arr, j, j + 1);
|
||
hasSort = false; // 交换元素之后，设置标志位为无序状态
|
||
swapPos = j; // 记录最后一次交换的元素的位置
|
||
}
|
||
}
|
||
if (hasSort === true) {
|
||
break;
|
||
}
|
||
k = swapPos; // 把最后一次交换的位置给k，之后的排序支队1 - n-k的元素进行比较，因为之后的元素都是有序的
|
||
}
|
||
}
|
||
|
||
// 鸡尾酒排序(冒泡排序变形)
|
||
export function cocktailSort(arr) {
|
||
let left = 0;
|
||
let right = arr.length - 1;
|
||
let index;
|
||
while (left < right) {
|
||
// 大的排在后面
|
||
for (let i = left; i < right; i++) {
|
||
if (arr[i] > arr[i + 1]) {
|
||
swap(arr, i, i + 1);
|
||
index = i;
|
||
}
|
||
}
|
||
// 第一轮排完之后index右侧的数字都是有序的,只需从index开始排就行（重点）
|
||
right = index;
|
||
// 小的排前面
|
||
for (let i = right; i > left; i--) {
|
||
if (arr[i] < arr[i - 1]) {
|
||
swap(arr, i, i - 1);
|
||
index = i;
|
||
}
|
||
}
|
||
left = index;
|
||
}
|
||
}
|