插入排序的基本思想是，每次将一个待排序元素插入到前面已经排好序元素中的适当位置，直到全部元素插入完成为止。其中，直接插入排序是最简单的插入排序。
将待排序的数组R[0..n-1]分为两个部分[0..i-1]和[i..n-1]。其中[0..i-1]为有序区间，[i..n-1]为无序区间。
对于第i趟排序（这里规定第一趟排序从R[1]开始毕竟一个单独字符R[0]不需要排序嘛！），[0..i-1]已经为有序区间。将元素R[i]分别于之前的每一个元素进行比较，在有序区找到合适的位置后，将R[i]插入该位置。
注：比较顺序可以从0到i-1，也可以从i-1到0。本例将以i-1到0为例。
最坏情况：一开始元素就是有序从大到小的，时间复杂度为O(n^2^)
最好情况：一开始元素就是有序从小到大的，时间复杂度为O(n)
空间复杂度：
只使用了i，j，tmp三个辅助变量，与问题规模n无关。空间复杂度为O(1)
插入时判断条件为R[i]tmp，故相同元素的相对位置不变。这是一种稳定的排序方法。