活动地址：CSDN21天学习挑战赛
作者简介：大家好我是小唐同学(๑><๑），大家可以叫我小唐
个人主页：小唐同学(๑><๑）的博客主页
系列专栏：数据结构
博友们如果也是新手入门数据结构我希望大家可以多加练习 数据结构题库在牛客网就有已经给大家附上链接，可以直接点击跳转：刷题点这里
牛客网支持ACM模式哦，刷算法题也很推荐哦！！！
下面上文章------》
目录
概念：
直接插入排序：直接插入排序是一种最简单的排序方法，过程就是将每个待排元素逐个插入到已经排好的有序序列中。
算法输入和输出：
输入：
n个数的序列，通常直接存放在数组中，可能是任何顺序。
输出：
输入序列的一个新排列，满足从小到大的顺序（默认讨论升序，简单的修改就可以实现降序排列）。
算法思想：
每次我们从原有数据中取出一个数，插入到之前已经拍好的序列中，直到所有数全部取完，那么新的有序排列也就完成了。
实例：
我们先给出实例数组：
1 5 9 2 6 8 12
当有序数列中无元素是 则首元素 1 则为有序列
1 5 9 2 6 8 12
则首个无序元素 5 进入有序列 与有序列进行比较
1 5 9 2 6 8 12
则首个无序元素 9 进入有序列 与有序列进行比较
1 5 9 2 6 8 12
则首个无序元素 2 进入有序列 与有序列进行比较
1 2 5 9 6 8 12
以此类推
则可得出有序列
1 2 5 6 8 9 12
代码实现：
# include <stdio.h> int main() { int n; scanf("%d",&n); int a[n]; for (int i=0;i<n;i++) { scanf("%d",&a[i]); } int temp; for(int i=1;i<n;i++) { if(a[i]<a[i-1]) { int j; temp=a[i]; for(j=i-1;j>=0&&temp<a[j];j--) { a[j+1]=a[j]; } a[j+1]=temp; } } for(int i=0;i<n;i++) { printf("%d",a[i]); } }
白话解析核心代码：
白话讲解直接插入排序核心算法：
i从1开始
当a[i]<a[i-1]时说明
后边的元素小于前边的元素
那就要提前
把该值进行暂时存储temp
进行for循环从后向前进行比较
只要比temp (a[i])大 则继续向前比较 把 j+1的位置进行向后填充（也就是比a[i]大的放后边）
当temp不小于a[j]时则跳出
把temp赋值给j+1
for(int i=1;i<n;i++) { if(a[i]<a[i-1]) { int j; temp=a[i]; for(j=i-1;j>=0&&temp<a[j];j--) { a[j+1]=a[j]; } a[j+1]=temp; }
时间复杂度：
最好的状态是:有序的的序列 只需要从头到尾遍历一遍时间复杂度为 O（n）
最差的状态是：全部乱序 均需要交换 时间复杂度为O(n*n)
空间复杂度：
算法中要用辅助空间 且为常量
空间复杂度为：O（1）
