插入排序
实现原理：
将数组分成‘已排序’和‘未排序’两个部分，一开始的时候，‘已排序’的部分只有一个元素，然后将它后面的一个元素从‘未排序’部分插入‘已排序’部分，从而将‘已排序’部分增加一个元素，而‘未排序’部分减少一个元素。以此类推完成排序
<font color=red>可以类比斗地主</font>
代码实现:
const insertionSort = (targetArr) => {
const changePosition = (arr, index1, index2) => {
[arr[index1], arr[index2]] = [arr[index2], arr[index1]]
}
let sortedArr = []
sortedArr.push(targetArr.shift())
for (let i = 0; i < targetArr.length; i ++) {
sortedArr.push(targetArr[i])
for (let j = sortedArr.length - 1; j >= 0; j --) {
if (sortedArr[j] < sortedArr[j - 1]) {
changePosition(sortedArr, j, j-1)
}
}
}
return sortedArr
}
时间复杂度: O(n^2)
