一、算法实现原理
1.排序原理
将元素直接对已经有序序列（默认数组第一个元素为初始有序序列）进行遍历比较，直接插入到相应位置，插入位置之后的元素顺序后移一位，经过n-1趟插入完成排序。
例：
2.改进思路
根据直接插入排序算法的实现原理可知，算法的时间主要耗费在了寻找元素待插入位置上，如果能够将这部分的时间降下来，那么就可以有效的提高算法速度。
而直接插入排序的主要应用场景就是在序列本身基本有序的情况下，算法在查找待插入位置时进行的比较和元素搬移操作较少。所以我们就可以通过一些方法来将序列调到基本有序的情况，即可提高算法的效率，由此前辈大佬设计出了希尔排序，具体实现可参照后续博文。
二、代码实现
1.完整代码
#include<stdio.h> void InsertSort(int* array, int size);//直接插入排序 void Print_Array(int* array, int size);//打印数组 int main() { int array[] = { 3,1,5,8,4,0,2,7,6,1 }; int length = sizeof(array) / sizeof(array[0]); printf("排序前："); Print_Array(array, length); InsertSort(array, length); printf("\n排序后："); Print_Array(array, length); return 0; } void InsertSort(int* array, int size) {//直接插入排序 for (int i = 1; i < size; i++) {//从1开始循环，默认数组内第一个元素为有序序列 int end = i - 1;//标记已排序序列最后位置下标 int key = array[i];//依次拿取数组内元素 while (end >= 0 && key < array[end]) {//key从前往后比较：小于当前元素，继续往前走 array[end + 1] = array[end];//将当前元素往后移一个位置 end--; } array[end + 1] = key;//key大于等于当前元素，插入到当前位置之后 } } void Print_Array(int* array, int size) {//打印数组 for (int i = 0; i < size; i++) { printf("%d ", array[i]); } }
2.测试结果
三、性能分析
1.元素集合越接近有序，直接插入排序算法的时间效率越高。
2.时间复杂度：
3.空间复杂度：O(1)
4.稳定性：稳定
