前言
直接插入排序是属于插入排序类的一种，这种排序的方法相对较为简单，实现起来较为容易。直接插入排序的算法思想有点类似于我们平时打牌摸牌的操作，将新摸上来的牌插入到原先已经有序的区间里面，使得其仍然有序。下面我们将介绍直接插入排序的具体思想和实现方法，以及其时间复杂度、空间复杂度和稳定性。
一、直接插入排序的基本思想
基本思想： 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。
二、直接插入排序代码实现
void InsertSort(int* a, int n)
{
for (int i = 0; i < n-1; i++)
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
三、直接插入排序的复杂度分析
时间复杂度： 我们首先来看直接插入排序的最好的情况，也就是当待排序的数据是顺序有序的时候，也就是不需要排序就已经是所要求的有序了，在这种情况下直接插入排序仍然需要对所有数据进行一次遍历，时间复杂度是O(N)；再来看最坏的情况，也就是当待排序的数据是逆序有序的时候，也就是说从头到尾每一个数据我们都需要去向后挪动，然后再插入数据，这种情况下的时间复杂度是O(N2)，由于时间复杂度算的是最坏的情况，因此直接插入排序的时间复杂度是O(N2)。
空间复杂度： 由于直接插入排序没有开辟额外的空间，因此直接插入排序的空间复杂度是O(1)。