优化：当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作。
// 冒泡排序（已优化） const bubbleSort2 = arr => { console.time('改进后冒泡排序耗时'); const length = arr.length; if (length <= 1) return; // i < length - 1 是因为外层只需要 length-1 次就排好了，第 length 次比较是多余的。 for (let i = 0; i < length - 1; i++) { let hasChange = false; // 提前退出冒泡循环的标志位 // j < length - i - 1 是因为内层的 length-i-1 到 length-1 的位置已经排好了，不需要再比较一次。 for (let j = 0; j < length - i - 1; j++) { if (arr[j] > arr[j + 1]) { const temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; hasChange = true; // 表示有数据交换 } } if (!hasChange) break; // 如果 false 说明所有元素已经到位，没有数据交换，提前退出 } console.log('改进后 arr :', arr); console.timeEnd('改进后冒泡排序耗时'); };测试
// 测试 const arr = [7, 8, 4, 5, 6, 3, 2, 1]; bubbleSort(arr); // 改进前 arr : [1, 2, 3, 4, 5, 6, 7, 8] // 改进前冒泡排序耗时: 0.43798828125ms const arr2 = [7, 8, 4, 5, 6, 3, 2, 1]; bubbleSort2(arr2); // 改进后 arr : [1, 2, 3, 4, 5, 6, 7, 8] // 改进后冒泡排序耗时: 0.318115234375ms分析
第一，冒泡排序是原地排序算法吗 ？
冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为 O(1)，是一个原地排序算法。
第二，冒泡排序是稳定的排序算法吗 ？
在冒泡排序中，只有交换才可以改变两个元素的前后顺序。
为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序。
所以冒泡排序是稳定的排序算法。
第三，冒泡排序的时间复杂度是多少 ？
最佳情况：T(n) = O(n)，当数据已经是正序时。
最差情况：T(n) = O(n2)，当数据是反序时。
平均情况：T(n) = O(n2)。
动画
插入排序又为分为 直接插入排序 和优化后的 拆半插入排序 与 希尔排序，我们通常说的插入排序是指直接插入排序。
一、直接插入
思想
一般人打扑克牌，整理牌的时候，都是按牌的大小（从小到大或者从大到小）整理牌的，那每摸一张新牌，就扫描自己的牌，把新牌插入到相应的位置。
插入排序的工作原理：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
步骤
从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤 2~5。
实现
// 插入排序 const insertionSort = array => { const len = array.length; if (len <= 1) return let preIndex, current; for (let i = 1; i < len; i++) { preIndex = i - 1; //待比较元素的下标 current = array[i]; //当前元素 while (preIndex >= 0 && array[preIndex] > current) { //前置条件之一: 待比较元素比当前元素大 array[preIndex + 1] = array[preIndex]; //将待比较元素后移一位 preIndex--; //游标前移一位 } if (preIndex + 1 != i) { //避免同一个元素赋值给自身 array[preIndex + 1] = current; //将当前元素插入预留空位 console.log('array :', array); } } return array; };测试
// 测试 const array = [5, 4, 3, 2, 1]; console.log("原始 array :", array); insertionSort(array); // 原始 array: [5, 4, 3, 2, 1] // array: [4, 5, 3, 2, 1] // array: [3, 4, 5, 2, 1] // array: [2, 3, 4, 5, 1] // array: [1, 2, 3, 4, 5]分析
第一，插入排序是原地排序算法吗 ？
插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是 O(1)，所以，这是一个原地排序算法。
第二，插入排序是稳定的排序算法吗 ？
在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。