1.冒泡排序（常考）

认识

冒泡排序（Bubble Sort）是一种非常直观且简单的排序算法，主要用于对一组数据进行排序。它的名字来源于这样一个过程：在每一轮遍历中，最大的元素会“像气泡一样”逐渐上浮到数组的末端，故称为“冒泡排序”。

原理如下

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个，如果不是相等的就跳过比下面的元素 ，这样依次的循环下去 直到所有的元素都比较完成才结束。
2. 针对所有的元素重复以上的步骤，除了最后一个。
3. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

思路

冒泡排序其实核心是对比里面的一层，就是谁大排后面
加一层外面的排序步骤，因为两个对比，所以最后一个不需要对比，对比次数就是数组长度减一

实际手写

function bubbleSort(arr) {
    const len = arr.length
    if (len <= 1) return

    for (let i = 0; i < len - 1; i++) {
        for (let j = 0; j < len - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                const temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }
        }
    }
}

// 功能测试
const arr = [4, 3, 6, 2, 5, 7, 9, 8, 1]
bubbleSort(arr)
console.log(arr) // [1, 2, 3, 4, 5, 6, 7, 8, 9]

整个交换过程比较,分别对比

// 14 34  46 62 65 98 
// 1 3 4 2 5 6 7 8 9 
// 1 3 2 4 56789

优化写法

 // 优化1 写法
  function bubbleSort(arr) {
      const len = arr.length
      if (len <= 1) return
      for (let i = 0; i < len - 1; 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]]
              }
          }
      }
  }

我们可以添加一个计算步数的看看我们的步数走了多少，这个过程可以看出我们部署总共走了36步

function bubbleSort(arr) {
        const len = arr.length
        let stepCount = 0; // 步数计数器
        if (len <= 1) return
        for (let i = 0; i < len - 1; i++) {
            for (let j = 0; j < len - i - 1; j++) {
                stepCount++; // 每次比较都算一步
                if (arr[j] > arr[j + 1]) {
                  [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
                }
            }
        }
        console.log(stepCount,'步数');
        return arr
}

// 输出
36 '步数'

优化逻辑-添加有序标志减少遍历次数

我们发现，虽然我们一直对比，但是后面其实我们已经排序好的并不需要太多的对比，所以我们可以添加一个有序标志

如果一轮遍历中没有发生任何交换，说明数组已经有序，可以提前结束排序

这个时候我们优化一下可以发现，步数已经缩减到了26步

原理

这个标志用来判断在某一轮遍历中是否发生了元素交换
如果一轮遍历中没有发生任何交换，说明数组已经有序，可以提前结束排序

例子：
假设数组是 [1, 2, 3, 4, 5]，在第一轮遍历时：

比较1和2，不交换
比较2和3，不交换
比较3和4，不交换
比较4和5，不交换
整个过程中 isSorted 始终为true
因此排序提前结束，不需要进行后续的遍历

// 优化2 标志上一次移动的下标 有序标志 (isSorted)
  function bubbleSort(arr) {
      const len = arr.length;
      let stepCount = 0; // 步数计数器
      if (len <= 1) return
      for (let i = 0; i < len - 1; i++) {
          let isSorted = true // 有序标志
          for (let j = 0; j < len - i - 1; j++) {
              stepCount++; // 每次比较都算一步
              if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
                isSorted = false
              }
          }
          if (isSorted) {
              console.log(isSorted, '交换结束===isSorted');
              break
          } // 如果没有发生交换，说明已经有序
      }
      console.log(stepCount,'步数');
      return arr
  }
// 输出 26 '步数'

优化逻辑-添加无序边界 (sortBorder) 减少每次遍历的比较次数

标记上一轮已经有序的位置 ,我们可以通过记录无序数列的边界位置

下一轮遍历时只需要比较到这个位置即可，因为后面的元素已经有序

例子： 
假设数组是 [3, 4, 2, 1, 5]：

第一轮遍历：

3和4比较，不交换
4和2比较，交换，数组变为 [3, 2, 4, 1, 5]，lastSwapIndex = 2
4和1比较，交换，数组变为 [3, 2, 1, 4, 5]，lastSwapIndex = 3
4和5比较，不交换
第一轮结束后，sortBorder = 3，因为最后一次交换发生在索引3
此时我们知道，索引3之后的元素(4,5)已经有序
第二轮遍历：

只需要比较到索引3即可，不需要比较到最后
3和2比较，交换，数组变为 [2, 3, 1, 4, 5]，lastSwapIndex = 1
3和1比较，交换，数组变为 [2, 1, 3, 4, 5]，lastSwapIndex = 2
3和4比较，不交换
第二轮结束后，sortBorder = 2，因为最后一次交换发生在索引2
此时我们知道，索引2之后的元素(3,4,5)已经有序

这个时候输出我们发现，步数已经优化到了18步，也就是刚刚开始时候我们36步的一般，效率提升100%

    // 优化3 标记上一轮已经有序的位置  无序边界 (sortBorder) 
    function bubbleSort(arr) {
        let stepCount = 0; // 步数计数器
        const len = arr.length;
        if (len <= 1) return arr;

        let sortBorder = len - 1; // 初始时无序边界为数组末尾
        let lastSwapIndex = 0; // 记录最后一次交换的位置

        for (let i = 0; i < len - 1; i++) {
            let isSorted = true; // 有序标志

            for (let j = 0; j < sortBorder; j++) {
                stepCount++; // 每次比较都算一步
                if (arr[j] > arr[j + 1]) {
                    [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                    isSorted = false; // 发生了交换，说明还不是完全有序
                    lastSwapIndex = j; // 记录最后一次交换的位置
                }
            }

            sortBorder = lastSwapIndex; // 更新无序边界，边界之后的元素已经有序
            if (isSorted) {
                console.log(isSorted, '交换结束===isSorted');
                break; // 如果没有发生交换，说明已经有序
            }
        }

        console.log(stepCount, '步数');
        return arr;
    }

    // 测试代码
    const testArr = [64, 34, 25, 12, 22, 11, 90];
    console.log('原始数组:', testArr);
    bubbleSort(testArr);


//输出 18 '步数'

添加上我们计算步数以及以及交换和对比的计数

 // 优化3 标记上一轮已经有序的位置  无序边界 (sortBorder) 
    function bubbleSort(arr) {
        let stepCount = 0; // 步数计数器
        let compareCount = 0; // 比较次数计数器
        let swapCount = 0; // 交换次数计数器

        const len = arr.length;
        if (len <= 1) return arr;
        let sortBorder = len - 1; // 初始时无序边界为数组末尾
        let lastSwapIndex = 0; // 记录最后一次交换的位置
        for (let i = 0; i < len - 1; i++) {

            let isSorted = true; // 有序标志

            for (let j = 0; j < sortBorder; j++) {

                stepCount++; // 每次比较都算一步
                compareCount++; // 每次比较都计数

                if (arr[j] > arr[j + 1]) {
                    [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                    isSorted = false; // 发生了交换，说明还不是完全有序
                    lastSwapIndex = j; // 记录最后一次交换的位置
                    swapCount++; // 每次交换都计数
                }
            }
            sortBorder = lastSwapIndex; // 更新无序边界，边界之后的元素已经有序
            if (isSorted) {
                console.log(isSorted, '交换结束isSorted');
                break; // 如果没有发生交换，说明已经有序
            }
        }

        console.log(stepCount, '步数');
        console.log('比较次数:', compareCount);
        console.log('交换次数:', swapCount);
        return arr;
    }

    // 功能测试
    const arr = [1, 4, 3, 6, 2, 5, 7, 9, 8]
    bubbleSort(arr)
    console.log(arr) // [1, 2, 3, 4, 5, 6, 7, 8, 9]