前言

冒泡排序是一种简单但有用的排序算法，它得名于其排序进程中较大或较小的元素像气泡一样逐步浮出到列表的顶部。尽管它在功率方面不如其他高级排序算法，但冒泡排序的原理易于理解和完结，因而在某些情况下依然被广泛应用。

冒泡排序

冒泡排序的基本思想十分直观。它经过屡次迭代比较相邻的元素，并根据需求交流它们的方位来进行排序。具体来说，算法会重复地遍历整个列表，每次遍历都将当时元素与其下一个元素进行比较。假如当时元素大于下一个元素，则交流它们的方位。经过这样的迭代，较大的元素会逐步”浮”到列表的顶部。

解构

数组解构是一种在JavaScript中从数组中提取值并将其赋给变量的语法。它答应咱们经过一种简洁的方法，将数组中的元素解构到单独的变量中。

具体来说，数组解构的语法运用方括号[]来匹配数组中对应方位的值，并将这些值赋给事先声明的变量。例如：

let a = 1,
    b = 2;
[a,b] = [b,a];
console.log(a,b);

在这段代码中，咱们运用解构赋值的方法交流了变量a和b的值。

首要，咱们界说了两个变量a和b，并别离赋值为1和2：

let a = 1,
    b = 2;

接下来，咱们运用解构赋值的语法[a, b] = [b, a]，将数组的第一个元素赋值给a，将数组的第二个元素赋值给b。因为解构赋值是同时进行的，因而在右侧的数组中，b的值现已被赋给了a，而a的值现已被赋给了b，完结了值的互换。

最终，咱们打印出变量a和b的值：

console.log(a, b); // 输出: 2, 1

因而，输出成果为2和1，阐明变量a和b的值现已成功交流。这种用法能够在不运用第三个变量的情况下交流两个变量的值，十分方便。

冒泡排序的完结

现在咱们有一个数组：

arr = [5,8,6,3,9,2,1,7]

怎么完结排序呢？信任不少人立马能够写出下面的代码：

function bubbleSort(arr) {
    let len = arr.length; 
    for(let i = 0; i < len; i++) { 
        for(let j = 0; j < len - i - 1; j++) {
        if(arr[j] > arr[j+1]) { 
            [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
        }
        }
    }
    return arr;
}
const arr = [5,8,6,3,9,2,1,7];
bubbleSort()

可能会有人不是很清楚为什么第四行代码为什么是j < len - i - 1?

这是因为在冒泡排序的进程中，每一轮内部循环都会将当时未排序部分中最大的元素移动到了末尾，因而每轮能够少比较一次。具体来说，第一轮需求比较n-1次，第二轮需求比较n-2次，以此类推，最终一轮只需求比较1次。所以，内层循环的完毕条件应该是j < len - i - 1。

例如，关于一个长度为8的数组，在第一轮循环中，需求比较8-1=7次，即从0到6；在第二轮循环中，只需求比较7-1=6次，即从0到5；在第三轮循环中，只需求比较6-1=5次，即从0到4；以此类推，最终一轮循环只需求比较1次，即从0到0。

因而，j < len - i - 1的条件能够确保每轮内部循环不会比较现已排好序的元素。这样能够削减冒泡排序的时刻复杂度。

冒泡排序的优化

尽管前面咱们现已完结了冒泡排序，但是咱们是否能够经过削减不必要的比较操作和提前完毕排序进程来提高算法的功率，使得改善后的冒泡排序算法在某些情况下具有更好的功能呢？

下面咱们看优化后的代码：

    function bubbleSort(arr) {
    console.time('改善冒泡排序');
    const length = arr.length;
    if (length <= 1) return;
    for (let i = 0; i < length - 1; i++) {
        let isSorted = true;
        for (let j = 0; j < length - i -1; j++) {
            if (arr[j] > arr[j+1]) {
                [arr[j] , arr[j+1]] = [arr[j+1], arr[j]];
                isSorted = false;
            }       
        }
        if (isSorted) {
            break;
        }
    }
    console.timeEnd('改善冒泡排序');
    return arr
}
const arr = [5, 8, 6,  3,  9, 2, 1, 7];
bubbleSort(arr)
// 5  8  6  3  9  2  1  7
// 5  6  3  8  2  1  7  9
// 5  3  6  2  1  7  8  9
// 3  5  2  1  6  7  8  9
// 3  1  2  5  6  7  8  9
// 1  2  3  5  6  7  8  9 
// 1  2  3  5  6  7  8  9 
// 1  2  3  5  6  7  8  9

咱们对原始的冒泡排序算法进行了以下优化：

引进一个标志位 isSorted，用于判别当时次序是否现已完结排序。假如在某一轮循环中没有产生元素交流，阐明数组现已有序，直接跳出循环，削减了不必要的比较操作。
在每一轮排序前都将 isSorted 标志位设置为 true，假如在内部循环中产生元素交流，就将 isSorted 设置为 false，表明当时次序产生了交流。这样能够经过检查 isSorted 来判别数组是否现已有序，避免了不必要的多余比较。
在进行内部循环时，关于现已排好序的部分元素，它们会逐步”冒泡”到数组的末尾，因而每一轮内部循环的比较次数能够逐步削减，从而提高了功率。

这些优化使得改善后的冒泡排序算法在某些情况下具有更好的功能。能够经过削减不必要的比较操作和提前完毕排序进程来提高算法的功率。

完整注释如下：

// 界说改善冒泡排序函数
function bubbleSort(arr) {
console.time('改善冒泡排序'); // 发动计时器，用于计算排序所花费的时刻
const length = arr.length; // 缓存数组长度
if (length <= 1) return; // 假如数组长度小于等于1，无需排序，直接回来
// 进行 length-1 轮排序
for (let i = 0; i < length - 1; i++) {
  let isSorted = true; // 增加一个标志位，用于判别当时次序是否现已完结排序
  // 每轮比较相邻元素
  for (let j = 0; j < length - i - 1; j++) {
    if (arr[j] > arr[j+1]) { // 假如前一个元素比后一个元素大
      [arr[j], arr[j+1]] = [arr[j+1], arr[j]]; // 交流它们的方位
      isSorted = false; // 标志方位为 false，表明当时次序产生了交流
    }       
  }
  if (isSorted) { // 假如当时次序没有产生交流，阐明数组现已有序，无需再进行排序
    break;
  }
}
console.timeEnd('改善冒泡排序'); // 停止计时器，并输出排序所花费的时刻
return arr; // 回来排序后的数组
}
const arr = [5, 8, 6, 3, 9, 2, 1, 7];
console.log(bubbleSort(arr)); // 输出排序后的数组

bubbleSort函数接受一个数组参数，用于进行排序操作。
console.time('改善冒泡排序')发动计时器，用于计算排序所花费的时刻。
const length = arr.length缓存数组长度。
if (length <= 1) return假如数组长度小于等于1，无需排序，直接回来。
for (let i = 0; i < length - 1; i++)进行 length-1 轮排序。
let isSorted = true增加一个标志位，用于判别当时次序是否现已完结排序。
for (let j = 0; j < length - i - 1; j++)每轮比较相邻元素。
if (arr[j] > arr[j+1])假如前一个元素比后一个元素大。
[arr[j], arr[j+1]] = [arr[j+1], arr[j]]交流它们的方位。
isSorted = false标志方位为 false，表明当时次序产生了交流。
if (isSorted)假如当时次序没有产生交流，阐明数组现已有序，无需再进行排序。
console.timeEnd('改善冒泡排序')停止计时器，并输出排序所花费的时刻。
return arr回来排序后的数组。
const arr = [5, 8, 6, 3, 9, 2, 1, 7]界说一个需求排序的数组。
console.log(bubbleSort(arr))输出排序后的数组。

冒泡排序的提高

在时刻复杂度相同的情况下，还能再进行优化和提高吗？
上面这段代码运用了两层嵌套的循环，外层循环操控履行的轮数，内层循环用于比较相邻元素并进行交流。在每一轮内部循环完毕后，经过判别 isSorted 变量是否为 true 来判别数组是否现已排好序。假如现已排好序，则直接退出外层循环。

咱们能够注意到上面代码其实在第六次内部循环就现已完结排序：

// 5  8  6  3  9  2  1  7
// 5  6  3  8  2  1  7  9
// 5  3  6  2  1  7  8  9
// 3  5  2  1  6  7  8  9
// 3  1  2  5  6  7  8  9
// 1  2  3  5  6  7  8  9 
// 1  2  3  5  6  7  8  9 
// 1  2  3  5  6  7  8  9

因为在每轮排序进程中，右边现已排好序的部分不需求再次比较，所以咱们能够引进一个变量来记录上一轮完结交流的最终一个方位，然后将这个方位作为下一轮内部循环的鸿沟，从而削减了比较次数。

所以得到下面代码：

const arr = [5, 8, 6, 3, 9, 2, 1, 7];
const bubbleSort = (arr) => {
  let tmp = 0; // 用于交流元素时的临时变量
  let lastExchangeIndex = 0; // 上一轮完结交流的最终一个方位
  let arrLen = arr.length; // 数组的长度
  let sortBorder = arrLen - 1; // 排序的鸿沟，初始为数组长度减一
  for (let i = 0; i < arrLen - 1; i++) { // 外层循环，操控排序轮数
    let isSorted = true; // 符号本轮排序是否现已有序
    for (let j = 0; j < sortBorder; j++) { // 内层循环，履行相邻元素比较和交流
      if (arr[j] > arr[j + 1]) { // 假如当时元素大于下一个元素，交流它们的方位
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        isSorted = false; // 本轮有元素交流，阐明数组没有有序
        lastExchangeIndex = j; // 更新上一次交流的方位
      }
    }
    sortBorder = lastExchangeIndex; // 设置下一轮排序的鸿沟为上一次交流的方位
    if (isSorted) { // 假如本轮没有产生元素交流，阐明数组现已有序，完毕排序
      break;
    }
  }
  return arr; // 回来排序后的数组
};
console.log(bubbleSort(arr)); // 输出排序成果

这段代码优化只需内容是：

引进lastExchangeIndex变量，记录上一次交流元素的方位，用来确认下一轮排序的鸿沟。
内层循环时，将排序的鸿沟设为上一次交流元素的方位，优化了排序规模。
当发现本轮没有进行元素交流时，阐明数组现已有序，能够直接完毕排序。

今日的内容就是这些啦~

震惊！原来冒泡排序还能这样……

前言

冒泡排序

解构

冒泡排序的完结

冒泡排序的优化

冒泡排序的提高

作者信息

震惊！原来冒泡排序还能这样……

前言

冒泡排序

解构

冒泡排序的完结

冒泡排序的优化

冒泡排序的提高

相关文章

Android Chrome Custom Tab（二）— 操作按钮自定义以及预加载

一块RTX 3090加速训练YOLOv5s，时间减少11个小时，速度提升20%

JVM篇： 堆

图像放缩算法之Seam Carving

作者信息

JVM篇：堆