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

本文涉及的产品
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
全局流量管理 GTM,标准版 1个月
云解析 DNS,旗舰版 1个月
简介: 数据结构之直接插入排序(白话解析核心代码)


订阅专栏

 

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


相关文章
|
1月前
|
搜索推荐 UED Python
实现一个带有昼夜背景切换的动态时钟:从代码到功能解析
本文介绍了一个使用Python和Tkinter库实现的动态时钟程序,具有昼夜背景切换、指针颜色随机变化及整点和半点报时功能。通过设置不同的背景颜色和随机变换指针颜色,增强视觉吸引力;利用多线程技术确保音频播放不影响主程序运行。该程序结合了Tkinter、Pygame、Pytz等库,提供了一个美观且实用的时间显示工具。欢迎点赞、关注、转发、收藏!
134 94
|
17天前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》图、查找、排序专题考点(含解析)
408考研——《数据结构》图,查找和排序专题考点选择题汇总(含解析)。
69 29
|
17天前
|
存储 机器学习/深度学习 人工智能
C 408—《数据结构》易错考点200题(含解析)
408考研——《数据结构》精选易错考点200题(含解析)。
93 27
|
1月前
|
SQL Java 数据库连接
如何在 Java 代码中使用 JSqlParser 解析复杂的 SQL 语句?
大家好,我是 V 哥。JSqlParser 是一个用于解析 SQL 语句的 Java 库,可将 SQL 解析为 Java 对象树,支持多种 SQL 类型(如 `SELECT`、`INSERT` 等)。它适用于 SQL 分析、修改、生成和验证等场景。通过 Maven 或 Gradle 安装后,可以方便地在 Java 代码中使用。
284 11
|
2月前
|
自然语言处理 搜索推荐 数据安全/隐私保护
鸿蒙登录页面好看的样式设计-HarmonyOS应用开发实战与ArkTS代码解析【HarmonyOS 5.0(Next)】
鸿蒙登录页面设计展示了 HarmonyOS 5.0(Next)的未来美学理念,结合科技与艺术,为用户带来视觉盛宴。该页面使用 ArkTS 开发,支持个性化定制和无缝智能设备连接。代码解析涵盖了声明式 UI、状态管理、事件处理及路由导航等关键概念,帮助开发者快速上手 HarmonyOS 应用开发。通过这段代码,开发者可以了解如何构建交互式界面并实现跨设备协同工作,推动智能生态的发展。
197 10
鸿蒙登录页面好看的样式设计-HarmonyOS应用开发实战与ArkTS代码解析【HarmonyOS 5.0(Next)】
|
2月前
|
PHP 开发者 容器
PHP命名空间深度解析:避免命名冲突与提升代码组织####
本文深入探讨了PHP中命名空间的概念、用途及最佳实践,揭示其在解决全局命名冲突、提高代码可维护性方面的重要性。通过生动实例和详尽分析,本文将帮助开发者有效利用命名空间来优化大型项目结构,确保代码的清晰与高效。 ####
75 20
|
3月前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
99 1
|
3月前
|
机器学习/深度学习 存储 人工智能
强化学习与深度强化学习:深入解析与代码实现
本书《强化学习与深度强化学习:深入解析与代码实现》系统地介绍了强化学习的基本概念、经典算法及其在深度学习框架下的应用。从强化学习的基础理论出发,逐步深入到Q学习、SARSA等经典算法,再到DQN、Actor-Critic等深度强化学习方法,结合Python代码示例,帮助读者理解并实践这些先进的算法。书中还探讨了强化学习在无人驾驶、游戏AI等领域的应用及面临的挑战,为读者提供了丰富的理论知识和实战经验。
116 5
|
3月前
|
存储 NoSQL 关系型数据库
Redis的ZSet底层数据结构,ZSet类型全面解析
Redis的ZSet底层数据结构,ZSet类型全面解析;应用场景、底层结构、常用命令;压缩列表ZipList、跳表SkipList;B+树与跳表对比,MySQL为什么使用B+树;ZSet为什么用跳表,而不是B+树、红黑树、二叉树
|
3月前
|
监控 Java 应用服务中间件
高级java面试---spring.factories文件的解析源码API机制
【11月更文挑战第20天】Spring Boot是一个用于快速构建基于Spring框架的应用程序的开源框架。它通过自动配置、起步依赖和内嵌服务器等特性,极大地简化了Spring应用的开发和部署过程。本文将深入探讨Spring Boot的背景历史、业务场景、功能点以及底层原理,并通过Java代码手写模拟Spring Boot的启动过程,特别是spring.factories文件的解析源码API机制。
133 2

热门文章

最新文章

推荐镜像

更多