JavaScript冒泡排序算法详解及优化162

冒泡排序算法 (Bubble Sort) 是一种简单直观的排序算法，其核心思想是反复遍历要排序的数列，比较相邻的两个元素，如果它们的顺序错误就把它们交换过来。通过反复遍历，最终将最大的元素“冒泡”到数列的末尾。虽然效率不高，但它易于理解和实现，非常适合用于学习排序算法的基本原理。

算法原理：

冒泡排序算法的工作过程如下：
比较相邻的元素。如果第一个比第二个大，就交换它们。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

JavaScript实现：

下面是JavaScript中冒泡排序算法的几种实现方式：

基本实现：
function bubbleSort(arr) {
let len = ;
for (let i = 0; i < len - 1; i++) {
for (let j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// 交换元素
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
let arr = [5, 2, 9, 1, 5, 6];
let sortedArr = bubbleSort(arr);
(sortedArr); // Output: [1, 2, 5, 5, 6, 9]

这段代码实现了最基本的冒泡排序算法。外层循环控制遍历次数，内层循环比较相邻元素并交换。 `len - 1 - i` 的使用是为了避免对已经排序好的元素进行重复比较，提高效率。

优化实现：

基本实现虽然简单易懂，但效率较低。我们可以进行一些优化：

1. 优化标志：添加一个标志位 `swapped`，如果在某一轮循环中没有发生交换，则说明数组已经有序，可以提前结束排序。
function bubbleSortOptimized(arr) {
let len = ;
let swapped;
for (let i = 0; i < len - 1; i++) {
swapped = false;
for (let j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) break; // 如果没有交换，说明已排序
}
return arr;
}

2. 鸡尾酒排序 (Cocktail Shaker Sort)：这是一种冒泡排序的改进算法，它在每一轮遍历中不仅从左到右比较，还从右到左比较，可以提高效率。但效率提升有限，且代码复杂度略有增加。

function cocktailShakerSort(arr) {
let left = 0;
let right = - 1;
let swapped;
do {
swapped = false;
for (let i = left; i < right; i++) {
if (arr[i] > arr[i + 1]) {
[arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
swapped = true;
}
}
if (!swapped) break;
right--;
swapped = false;
for (let i = right - 1; i >= left; i--) {
if (arr[i] > arr[i + 1]) {
[arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
swapped = true;
}
}
left++;
} while (swapped);
return arr;
}