直接插入排序的基本思想是：向一个有序序列中，插入 1 个元素之后，可以得到一个长度增加 1 的有序序列。即：将第一个元素看成一个有序序列，然后从第二个元素开始逐个进行插入，一直到整个序列有序。
直接插入排序的改进算法包括：二分插入排序、两路插入排序等。
直接插入排序的基本操作是移动数据元素。在最坏的情况下，也就是当整个序列倒序时，基本操作的频度是：
1 + 2 + ... + (n - 1) = n2 - n / 2
所以，直接插入排序的时间复杂度 T(n) = O(n2)
直接插入排序是一种原地排序算法，故空间复杂度是：O(1)