直接插入排序（C语言实现）
目录
1.直接插入排序介绍
2.实现思路
3.动图展示
4.代码实现 （升序）
单趟排序实现
单趟排序代码
直接插入排序函数
5.代码测试
6.时空复杂度分析
时间复杂度O(N^2)
空间复杂度O(1)
1.直接插入排序介绍
插入排序，又叫直接插入排序。实际中，我们玩扑克牌的时候，就用了插入排序的思想。
基本思想：
在待排序的元素中，假设前n-1个元素已有序，现将第n个元素插入到前面已经排好的序列中，使得前n个元素有序。按照此法对所有元素进行插入，直到整个序列有序。
但我们并不能确定待排元素中究竟哪一部分是有序的，所以我们一开始只能认为第一个元素是有序的，依次将其后面的元素插入到这个有序序列中来，直到整个序列有序为止。
2.实现思路
当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与 array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移
3.动图展示
4.代码实现 （升序）
单趟排序实现
这里end之前的数字默认已经排序完成
当插入数字大于前面数字，我们这。里采用极端情况，大于前面所有数字时
那么我们需要吧end 之前的数字往后移，end一直往前移，当end减到-1时，循环停止，tmp放到end+1的位置上。
如果只是大于前面部分代码，当end走到a[end]<tmp时，直接跳出循环，将a[end+1] = tmp;
单趟排序代码
void InsertSort(int* a, int n)
{int end;int tmp = a[end + 1];while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;
}这里只有当找到插入位置，和循环走完才会截止循环。
直接插入排序函数
这里我们让end从0开始，一个元素即是有序数组。i<n-1即可。小于n时会越界访问，tmp = a[end+1],i走到n-2时就已经让最后一个数进行插入排序了。
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 (tmp < a[end]){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;}
}5.代码测试
void TestInsertSort()
{int a[] = { 66,11,22,55,47,21,98,31,26,78 };printf("插入前\n");Print(a, sizeof(a) / sizeof(a[0]));printf("插入后\n");InsertSort(a, sizeof(a) / sizeof(a[0]));Print(a, sizeof(a) / sizeof(a[0]));
}int main()
{TestInsertSort();} 
6.时空复杂度分析
时间复杂度O(N^2)
最坏情况 ：如果数组是完全逆序的，那么每次插入操作都需要将元素移到已排序部分的开头。这就意味着对于第i个元素，可能需要进行i次比较和移动。这种情况下，算法的时间复杂度是O(N^2)，因为需要进行总计约1 + 2 + 3 + … + (n-1)次比较，这是一个n(n-1)/2的等差数列
最好情况 ：这种情况发生在数组已经完全有序时。在这种情况下，每次比较后，很快就会找到插入位置（在已排序元素的末尾），不需要进行额外的移动。因此，最好情况下插入排序的时间复杂度是O(N)，因为外层循环只会遍历一次数组，内层循环不会进行任何实际的比较和移动操作。
空间复杂度O(1)
插入排序的空间复杂度为O(1)，因为它是一个原地排序算法，不需要额外的存储空间来排序
插入排序特性总结
1. 元素集合越接近有序，直接插入排序算法的时间效率越高。
2. 时间复杂度：O(N^2)。
3. 空间复杂度：O(1)，它是一种稳定的排序算法。
4. 稳定性：稳定。