'''
插入排序原理：将待排序序列的第一个元素当做已排序序列，其他的元素当做未排序序列，取未排序的第一个元素与已排序的最后一个元素进行比较，如果未排序的第一个元素小于已排序的最后一个元素则交换位置，交换位置后继续与前一个相邻位置的元素进行比较，当不需要交换时，则次轮插入完成。继续循环上面步骤，每进行一轮插入，已排序的序列加1，未排序的序列减1，一直到列表中的元素全部被插入到已排序的序列中为止，插入排序完毕。
例如数组：
{38,65,97,76,13,27,49}，具体排序过程如下：
第1轮插入38以后：[38] 65 97 76 13 27 49
第2轮插入65以后：[38 65] 97 76 13 27 49
第3轮插入97以后：[38 65 97] 76 13 27 49
第4轮插入76以后：[38 65 76 97] 13 27 49
第5轮插入13以后：[13 38 65 76 97] 27 49
第6轮插入27以后：[13 27 38 65 76 97] 49
第7轮插入49以后：[13 27 38 49 65 76 97]
'''
时间复杂度：
插入排序中每一轮插入都需要移动到最左端,需要进行n-1轮"插入",每一轮"插入"需要向前比较和移动i次,i的平均值为n/2,
时间复杂度为T(n)=n(n-1)/2,再乘每次操作的步骤数,所以插入排序的时间复杂度为:
O(n²)
空间复杂度：O(1)
