0


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


活动地址: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)


本文转载自: https://blog.csdn.net/m0_61469860/article/details/126109563
版权归原作者 小唐同学(๑>؂<๑) 所有, 如有侵权,请联系我们删除。

“数据结构之直接插入排序(白话解析核心代码)”的评论:

还没有评论