前言

    冒泡排序是一种简单但有效的排序算法，它得名于其排序过程中较大或较小的元素像气泡一样逐渐浮出到列表的顶部。虽然它在效率方面不如其他高级排序算法，但冒泡排序的原理易于理解和实现，因此在某些情况下仍然被广泛应用。

冒泡排序

    冒泡排序的基本思想非常直观。它通过多次迭代比较相邻的元素，并根据需要交换它们的位置来进行排序。具体来说，算法会重复地遍历整个列表，每次遍历都将当前元素与其下一个元素进行比较。如果当前元素大于下一个元素，则交换它们的位置。通过这样的迭代，较大的元素会逐渐"浮"到列表的顶部。

解构

数组解构是一种在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 

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

1. 引入一个标志位 isSorted，用于判断当前轮次是否已经完成排序。如果在某一轮循环中没有发生元素交换，说明数组已经有序，直接跳出循环，减少了不必要的比较操作。
2. 在每一轮排序前都将 isSorted 标志位设置为 true，如果在内部循环中发生元素交换，就将 isSorted 设置为 false，表示当前轮次发生了交换。这样可以通过检查 isSorted 来判断数组是否已经有序，避免了不必要的多余比较。
3. 在进行内部循环时，对于已经排好序的部分元素，它们会逐渐"冒泡"到数组的末尾，因此每一轮内部循环的比较次数可以逐渐减少，从而提高了效率。

这些优化使得改进后的冒泡排序算法在某些情况下具有更好的性能。可以通过减少不必要的比较操作和提前结束排序过程来提高算法的效率。

完整注释如下：

// 定义改进冒泡排序函数
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)); // 输出排序结果

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

1. 引入lastExchangeIndex变量，记录上一次交换元素的位置，用来确定下一轮排序的边界。
2. 内层循环时，将排序的边界设为上一次交换元素的位置，优化了排序范围。
3. 当发现本轮没有进行元素交换时，说明数组已经有序，可以直接结束排序。

   ---

今天的内容就是这些啦~