插入排序

• 时间复杂度（平均）：O(n^2)
• 时间复杂度（最坏）：O(n^2)
• 时间复杂度（最好）：O(n)
• 空间复杂度：O(1)
• 稳定

算法

将未排序的元素取出，在已排序的数组中从后向前扫描，插入到合适的位置：

将第i个元素与之前i-1个元素依次（倒序）比较，将其插入到刚好比arr[i]小的元素后面

从第二个（i===1）元素开始一直比较到最后一个元素

比较过程中记录下第i个元素，依次向前比较时，如果第i-1个元素大于其时，将i-1个元素写入到第i个位置上。。。直到找到i-k个元素恰好不大于其时，将第i个元素写入到第i-k+1的位置

function insertionSort(arr) {
	for (let i = 1; i < arr.length; i++) {
		let perIndex = i - 1;
		let current = arr[i];
		while (perIndex >= 0 && arr[perIndex] > current) {
			arr[perIndex + 1] = arr[perIndex];
			perIndex--;
    }
    // 注意 perIndex 个元素小于 current，所以要写入在 perIndex+1 上
		arr[perIndex + 1] = current;
	}
	return arr;
}