插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。
（1）步骤
1. 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
2. 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
（2）动图演示
（3）直接插入排序的特性总结：
1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定
（4）C语言代码实现如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | #include <stdio.h>#include <stdlib.h>void InsertSort(int num[],int n){ int i,j,k; for(i=1;i<n;i++)//默认第一个是有序的 { k=num[i];//获取无序的元素 for(j=i-1;j>=0;j--) //在有序队列中从后往前一个个的比 { if(k>=num[j])//如果k比这个数大，就放在这个数的后面 { num[j+1]=k; break; } num[j+1]=num[j];//如果k比这个数小，那就把这个数后移 if(j==0) num[0]=k; } }}int main(){ int num[5]= {2,3,1,5,4}; InsertSort(num,5); for(int i=0; i<5; i++) { printf("%d\n",num[i]); } return 0;} |
如果我们编译并运行上述程序，那么它应该产生以下结果：
1 2 3 4 5 | 12345 |
作业：
| 1528 | 蓝桥杯算法提高VIP-插入排序 |
| 1714 | 数据结构-直接插入排序 |
| 1715 | 数据结构-折半插入排序 |
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程