前言
如果想深入了解的话建议先看看 算法概述
为了方便用来测试的数组一成不变，我们可以来一个随机数组
const arr = []
const arrLength = 11 //可以随机长度 Math.floor(Math.random() * 30) + 1
for (let i = 0; i < arrLength; i++) {
arr.push(Math.floor(Math.random() * 99) + 1)
}
console.log(arr, 'arr')
算法描述
此算法的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
动图演示
代码实现
//插入
function insertionSort(arr) {
const len = arr.length;
let preIndex, current;
for (var i = 1; i < len; i++) {
preIndex = i - 1;
current = arr[i];
while (preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex + 1] = current;
}
return arr;
}
console.log(bubbleSort(arr),'bubbleSort arr')
优化思考
观察发现 次数 count 和 数组长度 length 的关系不是固定的，主要取决于数组的有序度
最坏情况下对比次数：count = (length-1)*length/2
最好情况下对比次数：count = length-1
那么上面要怎么优化呢？
我们上面的插入点是通过遍历查找的，现在我们可以在寻找插入点时采用了折半查找，称为折半插入排序（Binary Insertion Sort）
算法描述：
-
有一组数据待排序，排序区间为
Array[0]~Array[n-1]。 -
将数据分为有序数据和无序数据，第一次排序时默认
Array[0]为有序数据，Array[1]~Array[n-1]为无序数据。 -
有序数据分区的第一个元素位置为
low，最后一个元素的位置为high。 -
遍历无序区间的所有元素，每次取无序区间的第一个元素
Array[i]，因为0 ~ i-1是有序排列的，所以用中点m将其平分为两部分，然后将待排序数据同中间位置为m的数据进行比较。 -
若待排序数据较大，则
low~m-1分区的数据都比待排序数据小， -
反之，若待排序数据较小，则
m+1~high分区的数据都比 待排序数据大。 -
此时将
low 或 high重新定义为新的合适分区的边界，对新的小分区重复上面操作。 -
直到
low 和 high的前后顺序改变，此时high+1所处位置为待排序数据的合适位置。
//插入
function insertionSort(arr) {
var len = arr.length;
let i, j, temp, m, low, high;
for (i = 1; i < len; i++) {
temp = arr[i];
low = 0; high = i - 1;
while (low <= high) {
m = parseInt((low + high) / 2);
if (arr[m] > temp)
high = m - 1;
else
low = m + 1;
}
//替换位置后的元素往后移动一位，留出位置来
for (j = i - 1; j >= high + 1; j--)
arr[j + 1] = arr[j];
arr[j + 1] = temp;
}
return arr;
}
console.log(bubbleSort(arr),'bubbleSort arr')
二分插入排序是稳定的与二分查找的复杂度相同，这里我们就不展开说了
PS：其实希尔排序法就是对直接插入排序法的优化，是第二种优化方案
复杂度
最坏时间复杂度：O(n2)
最好时间复杂度：O(n)
评价时间复杂度：O(n2)
空间复杂度：O(1)
稳定性：稳定
