01冒泡排序

冒泡排序算法步骤：

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

以下面5个无序的数据为例：
40 8 15 18 12 （文中仅细化了第一趟的比较过程）
第1趟: 8 15 18 12 40

第一趟对比过程.png

第2趟: 8 15 12 18 40
第3趟: 8 12 15 18 40
第4趟: 8 12 15 18 40

let arr = [40, 8, 15, 18, 12];

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
      console.log('排序前：'+arr);
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        console.log('排序中!!调整：'+arr);
      }else{
        console.log('排序中!!不调整：'+arr);
      }
    }
    console.log('排序后：'+arr);
    console.log('-------------------');
  }
  console.log('最终结果:'+arr);

  return arr;
}
bubbleSort(arr);

最佳情况：T(n) = O(n)
当输入的数据已经是正序时（都已经是正序了，何必还排序呢….）

最差情况：T(n) = O(n2)
当输入的数据是反序时(哦天，我直接反序不就完了….)

平均情况：T(n) = O(n2)

平均时间复杂度：O(n2)
空间复杂度：O(1) (用于交换)
稳定性：稳定

沉底的操作 一次遍历会将最大的值找到放在最后一位 第二次找到第二大

排序前：40,8,15,18,12
排序中!!调整：8,40,15,18,12
排序中!!调整：8,15,40,18,12
排序中!!调整：8,15,18,40,12
排序中!!调整：8,15,18,12,40
排序后：8,15,18,12,40 //第一次遍历结束找到最大40
-------------------
排序前：8,15,18,12,40
排序中!!不调整：8,15,18,12,40
排序中!!不调整：8,15,18,12,40
排序中!!调整：8,15,12,18,40
排序后：8,15,12,18,40 //第二次遍历结束找到次大18
-------------------
排序前：8,15,12,18,40
排序中!!不调整：8,15,12,18,40
排序中!!调整：8,12,15,18,40
排序后：8,12,15,18,40 //第三次遍历结束找到次次大15
-------------------
排序前：8,12,15,18,40
排序中!!不调整：8,12,15,18,40
排序后：8,12,15,18,40
-------------------
最终结果:8,12,15,18,40

为什么内部循环是arr.length - i - 1因为前一次循环会找到最大值，所以每次循环都可以减少最后几项的对比。

image.png