随笔记：插入排序 --from wcc

插入排序

插入排序（ insertion sorting）是一种从序列左端开始依次对数据进行排序的算法。在排序过程中，左侧的数据陆续归位，而右侧留下的就是还未被排序的数据。插入排序的思路就是从右侧的未排序区域内取出一个数据，然后将它插入到已排序区域内合适的位置上。

思路：
1.默认从 i = 1 开始判断，这样 preIndex 自然是内部循环的游标；

2.current 保存 arr[i]，通过循环来确定 current 的最终位置；

3.每个内循环开始的时候，arr[i] === current === arr[preIndex + 1]，所以在内循环首次时 arr[preIndex + 1] = arr[preIndex] 的时候不必担心 arr[i] 的值丢失；

4.总体思路是，需要排位的元素先额外缓存起来，然后套用内循环，使得需要调整的元素赋值给它后面的一个位置上，形成依次挪位，
最后因为内循环在判断条件不生效的时候停止意味着找到了需要排位的元素的正确位置，然后赋值上去，完成排序

人类最伟大的地方就在于总能想出办法解决问题 --wcc