插入排序：
插入排序（英语：Insertion Sort）是一种简单直观的排序算法。 它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
基本思想
每一步都是将 待排序的一个数据，插入到一个已经有序的数据序列里面。直到所有的数据全部插入为止。【每一次插入都会进行一次排序】
类似于打牌【斗地主】，每摸一张就按照顺序放到位置。每摸一张牌之后一定是有序的，下一张牌来了，在已知的有序序列里面放到合适的位置。
插入排序方法
在插入 a[i]数据之前。a[0] ~a[i-1]一定是有序的。
现在需要插入a[i]这个数据，需要再a[0]~a[i-1]找到合适的位置放置a[i]，比如这个index为j，将a[i]放在索引j上面。
插入排序有多种：
1，简单插入排序 (每一次从后往前扫描每一个数据，确认插入位置的索引)
var simpleInsertSort = (arr
) => {
if (!arr
|| arr
.length
=== 1) return arr
let key
, j
;
for (let i
= 1; i
< arr
.length
; i
++) {
key
= arr
[i
];
for (j
= i
- 1; j
>= 0 && arr
[j
] > key
; j
--) {
arr
[j
+1] = arr
[j
]
}
arr
[j
+1] = key
}
return arr
}
2，二分插入排序 (因为前面已经是有序的，确定位置可以用二分法来确定)
var binaryInsertSort = (arr
) => {
if (!arr
|| arr
.length
=== 1) return arr
let key
;
for (let i
= 1; i
< arr
.length
; i
++) {
key
= arr
[i
];
let low
= 0, high
= i
- 1;
while(low
<= high
) {
let mid
= Math
.trunc((low
+ high
) / 2)
if (arr
[mid
] > key
) {
high
= mid
- 1
} else {
low
= mid
+ 1
}
}
for (let j
= i
- 1; j
>= high
+ 1; j
--) {
arr
[j
+ 1] = arr
[j
]
}
arr
[high
+1] = key
}
return arr
}
