数据结构之直接插入排序（白话解析核心代码）

​
​

活动地址：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）