排序算法之——插入排序
前置知识
现实生活中， 我们都玩过扑克牌 (友情提示： 为了自己和家人， 远离黄赌毒)， 我们逐一 从桌上拿起一张扑克， 然后 按照顺序，插入到手里已有的牌中， 形成了我们的想要的结果 比如：炸弹， 顺子等等。
插入排序
插入排序: 对未排序的的数据中， 在已排序的序列中从后向前扫描， 找到相应的位置插入。
数据结构： 数组
步骤:
从第一个元素开始， 该元素认定为已经被排序了
取出下一个元素， 在已经排序的元素序列中从后向前扫描
如果 已排序的元素 大于 该元素， 那么将 已排序的元素 向后 移动
继续向前扫描， 重复第 3个步骤， 一直找到 已排序的元素 小于 或者 等于 该元素
将该元素 插入到 新的位置
后续， 重复2-5的步骤， 直到完成整个排序
时间复杂度
平均时间复杂度 O(n2)O(n^{2})O(n2)
最坏时间复杂度 O(n2)O(n^{2})O(n2) （倒序）
最优时间复杂度 O(n)O(n)O(n) (升序)
图示
比如，有一组 无序数组: [6, 5, 3, 1, 8, 7, 2, 4]
第一步: 默认 第一个元素 6是已经排好序的
第二步: 取出 第二个元素 5， 然后向前扫描， 发现 6 > 5, 则 6向后移动一位， 此时发现 前面已经扫描结束， 那么 将 5放入到 当前位置
[5, 6, 3, 1, 8, 7, 2, 4]第三步： 取出 第三个元素 3， 然后向前扫描， 发现 6 > 3 ,那么 将 6 向后移动一位， 继续比较，发现 5 > 3, 那么将 5 向后移动一位, 此时 发现全部扫描结束， 那么 将3 放置到当前位置
[3, 5, 6, 1, 8, 7, 2, 4]第四步： 取出 第四个元素 1， 然后向前扫描， 发现 6 > 1 ,那么 将 6 向后移动一位， 继续比较，发现 5 > 1 ,那么 将 5 向后移动一位， 继续比较, ，发现 3 > 1 ,那么 将 3 向后移动一位，扫描结束， 那么 将 6 放置到当前位置
[1, 3, 5, 6, 8, 7, 2, 4]第五步： 取出 第五个元素 8， 然后向前扫描， 发现 8 > 6 ,扫描结束， 那么 将 8 位置不动
[1, 3, 5, 6, 8, 7, 2, 4]以此类推， 直到全部结束
[1, 2, 3, 4, 5, 6, 7, 8]'
代码实现（Typescript）
辅助工具 —— 生成随机数
function getRandomInteger(count: number = 1, min: number = 0, max: number = 1000): Array<number> { const res: Array<number> = [] for (let i = 0; i < count; i ++ ){ const random = Math.floor(Math.random() * (max - min) + min) res.push(random) } return res } 复制代码第一种: 及时交换数据
function insertSort(arr:Array<number>): Array<number> { if (arr.length <= 1) return arr for (let i = 1; i < arr.length; i++) { const curValue: number = arr[i] for (let j = i - 1; j >= 0; j--) { if (arr[j] > curValue) { arr[j + 1] = arr[j] arr[j] = curValue } } } return arr } 复制代码第二种: 记录索引， 遍历后集中更新数据
function insertSort(arr:Array<number>): Array<number> { if (arr.length <= 1) return arr for (let i = 1; i < arr.length; i++) { const curValue: number = arr[i] let currentIndex: number = i // 记录索引 for (let j = i - 1; j >= 0; j--) { if (arr[j] > curValue) { currentIndex = j // 更新当前索引位置 } } for (let k = i; k > currentIndex; k--) { arr[k] = arr[k-1] } arr[currentIndex] = curValue } return arr } 复制代码测试
const randoms: Array<number> = getRandomInteger(10) console.log("排序前:" + randoms) // 排序前:119,997,628,740,104,81,588,632,877,402 console.log("排序后:" + insertSort(randoms)) // 排序后:81,104,119,402,588,628,632,740,877,997
作者：请叫我张先森
链接：https://juejin.cn/post/7039546171857043492