简介英文名： Straight Insertion Sort
也是最简单的排序方法，基本操作是将记录插入到排列好的有序表中，得到记录数增加了1的新的有序表
步骤以数组2、5、8、3、6、9、1、4、7为例
从小到大排列
1 .先看前几，数组分为有序和无序部分先看前几个2，一个数必然是有序的，所以把2分成有序，后几个是无序的
2 .将无序部分的首端插入有序部分取出无序部分的首端，在有序部分由后向前比较，插入合适位置
3 .即使重复步骤2直到无序部分全部插入到有序8中，也可以通过一次比较插入
3需要多次比较。 注意要多次比较，直接插入。 一次插入一次而不是比较(与冒泡不同)。
后面的步骤也很简单，所以不再赘述
代码是从以上过程中得到的。 该算法遍历所有数一次，并分别插入，但初始数一定有序，无需排列。 因此，n个数字需要遍历n-1次。 也就是说，每当I直接从1开始时插入的比较从前面的数开始。 因此，可以直接将第二个循环的参数j设置为i-1
每次插入时首先取出要插入的数量
然后，在大于取出数情况下，将该数向后移动，j-1
-然后比较
此时再次比较的话，会出现小于3的数，如果退出循环，3就可以插入数组中。 下标是j 1
另一个摆脱循环的方法是，即使排在开头，也还没有出现小于取出数的数。 此时，直接退出循环，以1为例，-下一步根据规律2向后移动，j-1，此时j=-1也被退出循环，1置于下标j 1的位置，即第一步，与前一步一致
根据以上内容，有必要限定条件j=0和tempa[j]，最后使a[j 1]=temp
优化：如果要插入的数量大于前一个数量，则不需要先取出再放入
# include bits/stdc.husingnamespacestd； voidinsertsort(inta[]，int l ) { int temp； int j； for(intI=1； il； I () if ) a[I]a[I-1] ) { temp=a[i]； for(j=I-1； j=0tempa[j]； j--}{a[j1]=a[j]； } a[j 1]=temp； }for(intk=0； kl； k ) couta[k] '； coutendl； }}int main () inta [ 10 ]={ 2，5，8，3，6，9，1，4，7 }； intb [ 10 ]={ 1，2，3，4，5，6，7，8，9 }； int len=9； 插入(a，len )； 返回0； )特性1 )当时间复杂度最好时，一切都是有规律的。 在这种情况下，在一次遍历中，最佳时间复杂度为o(n ) o ) n ) o ) n
最坏的情况下全部为相反顺序，内层每次遍历被排序的部分，最坏的时间复杂度为o(n2 ) o ) n^2) o ) n2 )
综上所述，直接插入分类的平均时间复杂度为o(n2 ) o ) n^2) o ) n2 )
2 .空间复杂度辅助空间为常数
平均的空间复杂度为o(1) o )1) o )1)
3 .算法稳定性相同元素前后顺序是否改变
直接插入排序很稳定，因为要在比它大的数字之前插入
小测试是上面的代码，打印的数组如下所示
可以将代码更改为有序数组在后面，也就是从后向前扫描吗？
新算法，老办法，下次玩新花样怎么样？ （）