排序算法之二（插入排序）
Hello，大家好。忙了两天，今天终于有时间更新了，本期我主要讲解排序算法中的插入排序。
插播一条小惊喜，在写这篇文章时候，收到了心仪导师的回信，是我想要学习和研究的方向，起初调剂时候特别不甘，后来慢慢接受了这个结果，甚至现在开始期待研究生生活。意外的惊喜真的让人好开心，期待广州学习生活。
如果我的文章对您有帮助，希望可以帮忙转发，点击在看，给我更多的创作动力。
每周更新至少两篇。
· 插入排序原理 ·
插入排序非常好理解，对于给定的一组记录，初始时假设第一个记录自成一个有序序列，其余的记录为无序序列。接着从第二个记录开始，按照记录的大小一次将当前处理的记录插入到之前的有序序列中，直到最后一个记录插入到有序序列中为止。算法的原理如下：
（1）设置监视哨r[0]，将待插入记录的值赋值给r[0]；
（2）设置开始查找的位置j；
（3）在数组中进行搜索，搜索中将第j个记录后移，直至r[0] ≥ r[j]为止；
（4）将r[0]插入到r[j +1]的位置上；
以数组[38, 65, 97, 76, 13, 27, 49]为例，直接插入排序具体步骤如下：
第一步插入38以后：[38] 65 97 76 13 27 49
第二步插入65以后：[38 65] 97 76 13 27 49
第三步插入97以后：[38 65 97] 76 13 27 49
第四步插入76以后：[38 65 76 97] 13 27 49
第五步插入13以后：[13 38 65 76 97] 27 49
第六步插入27以后：[13 27 38 65 76 97] 49
第七步插入49以后：[13 27 38 49 65 76 97]
根据以上的原理，实现代码如下：
· 代码实现 ·
function insertSort(arr) {var tmp;for(var i = 1; i < arr.length; i++) {tmp = arr[i];for(var j = i - 1; j >= 0; j--) {if(tmp < arr[j]) {arr[j + 1] = arr[j];arr[j] = tmp;} else {break;}}}return arr;}var arr = [38, 65, 97, 76, 13, 27, 49], txt = "";for(var k in arr) {txt += arr[k] + " ";}console.log("排序前：" + txt);arr = insertSort(arr);txt = "";for(k in arr) {txt += arr[k] + " ";}console.log("排序后：" + txt);
算法的复杂度分析：
（1）最佳情况：T(n) = O(n)，当输入数组按升序排列，则是最佳情况。
（2）最差情况：T(n) = O(n^2)，当输入数组按降序排列是最差情况。
平均时间复杂度O(n²)，空间复杂度O(1)，占常数内存，不占额外内存，是一种稳定性的算法。
· 代码优化思路 ·
在查找插入位置时使用二分查找算法
function insertSort2() {var key, left, right, middle;for(var i = 1; i < arr.length; i++) {key = arr[i];left = 0;right = i - 1;while(left <= right) {middle = Math.floor((left + right)/2);if(key < arr[middle]) {right = middle - 1;} else {left = middle + 1;}}for(var j = i -1; j >= left; j--) {arr[j+1] = arr[j];}arr[left] = key;}return arr;}var arr = [38, 65, 97, 76, 13, 27, 49], txt = "";for(var k in arr) {txt += arr[k] + " ";}console.log("排序前：" + txt);arr = insertSort2(arr);txt = "";for(k in arr) {txt += arr[k] + " ";}console.log("排序后：" + txt);
每日鸡汤
热爱技术，坚持共享。
SLIGHT HEAT #2021#
Mose前端
新浪微博
CuiXin992173697