C/C++学习教程:C语言排序算法—插入排序算法_C语言C++学习交流群:1083227756-程序员宅基地

技术标签: C  1024程序员节  C语言  排序算法  插入排序  

前言:插入排序算法是所有排序方法中最简单的一种算法,其主要的实现思想是将数据按照一定的顺序一个一个的插入到有序的表中,最终得到的序列就是已经排序好的数据。

直接插入排序是插入排序算法中的一种,采用的方法是:在添加新的记录时,使用顺序查找的方式找到其要插入的位置,然后将新记录插入。

很多初学者所说的插入排序,实际上指的就是直接插入排序算法,插入排序算法还包括折半插入排序、2-路插入排序,表插入排序和希尔排序等。

 

直接插入排序的基本操作是将一个记录插入到已经排好的有序表中。

先选定一个位置i,插入排序将i左侧比位置i数值大的数值全部右移,然后将原来i对应的值插入回去。

 

voidInsertSort(int*p){int i,j;inttmp=0;for(i=1;i<10;i++)   

{if(p[i-1]>p[i])        {tmp = p[i];//将p[i]左边比p[i]大的全部左移,要先将其赋给一个缓存变量

for(j=i-1;p[j]>tmp;j--)         

  {p[j+1]=p[j];         

  }p[j+1]=tmp;     

  }    }}

过程,先将p[i]的值赋给tmp,然后i左侧的数值与tmp比较,比tmp大则右移一位,不比tmp大,则将tmp插入回去。

 

最好情况下,即要排序的序列本身是有序的,第7行的比较一共执行了n-1次,没有移动记录,时间复杂度为O(n)。

最坏情况下,需要比较2+3+...+n=(n+2)(n-1)/2次,移动次数为(n+4)(n-1)/2

 

时间复杂度为O(n2)

更多干货分享 有相关学习资料 请点击这里了解更多哦!!!

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_45713725/article/details/109265702

智能推荐

reactjs ajax库 推荐,如何确保数据在渲染ReactJS组件之前已通过AJAX加载?_Shi Hong的博客-程序员宅基地

我有一个父组件,名为UsersTable(它是其他组件的子项,并具有users和roles作为其道具)。 getRoles()函数正在为使用ajax请求的用户获取所有角色。结果返回到render()并存储在allroles变量中。问题是因为Ajax是异步的,我并不总是得到我需要的值在allroles变量。它有时为空或者为所有用户返回相同的值。我想我应该按照说明使用componentDidMount...

php读书笔记,PHP读书笔记整理_结构语句详解_鲁俊义的博客-程序员宅基地

PHP结构语句顺序结构顺序结构就像一条直线,按着顺序一直往下执行。我们编写的代码默认都是按照顺序结构执行的。条件结构之if…else…条件结构就像一个岔路口,可以向左走,也可以向右走。比如上洗手间,我们知道我们的性 别,这时候我们需要根据洗手间提供的条件,左边男洗手间,右边女洗手间,或者正好相反,其中性别就是这个条件结构的条件。再比如,现在的分数都流行使用 A、B、C来分级,假设考试成绩是93分,...

计算机网络规划_weixin_34381687的博客-程序员宅基地

一、 目前状况及前景:1、 公司主要分为关东和微型两大块,两地相距数公里,通信频繁,两地都有ADSL接入;2、 共有信息点240多个,分布在各个区域;3、 公司的网络建设主要是为即将上马的ERP应用服务;4、 将来要对相距数十公里的电镀部、子...

字体css样式在线,CSS Fonts(字体)_日本狸猫田中裕之的博客-程序员宅基地

CSS Fonts(字体)CSS字体属性允许您为字体设置各种样式,例如文本的字体系列,大小和粗体,变体等。字体属性在CSS样式为文本内容的字体,如提供几个属性:font-family,font-style,font-variant,font-weight和font-size。下一节将逐一介绍这些属性。字体系列该font-familyCSS属性允许您设置文本内容的字体系列名称,字体使用的优先级列表。...

Python简单爬虫导出CSV文件_藏何的专栏-程序员宅基地_python爬虫导出csv

核心代码: ####写入Csv文件中 with open(self.CsvFileName, 'wb') as csvfile: spamwriter = csv.writer(csvfile, dialect='excel') #设置标题 spamwriter.writer

手把手教你用VMware在linux下安装oracle10g RAC(6)-配置Clusterware安装环境_cqbh2011的博客-程序员宅基地

1、设置ssh在clusterware(CRS)和RacDatabase安装过程中,OracleUniversalInstaller(OUI)必须能够以oracle的身份自动将软件复制到所有RAC节点...

随便推点

RestTemplate用法-基本认证、JWT Token认证、自动重试_ory001的博客-程序员宅基地_resttemplate token认证

RestTemplate自定义拦截器1.基本认证 /** * @param builder * @return * @see BasicAuthenticationInterceptor * @see {@code RestTemplateBuilder#addClientHttpRequestInitializer(org.springframework.web.client.RestTemplate) } */ @Bean publi

如果失败的人生可以F5,如果莫名的悲伤可以DEL……………………_Kenzie 专栏-程序员宅基地

如果失败的人生可以F5,如果莫名的悲伤可以DEL;如果逝去的岁月可以CTRL+C,如果甜蜜的往事可以CTRL+V;如果一切都可以CTRL+ALT+DEL;那么我们所有的故事都不会ALT+F4?

dropzone实现拖放文件上传并预览图片_ful1021的专栏-程序员宅基地_dropzone预览

JS代码Dropzone.options.myDropzone = { //指定处理上传图片的路径 url: "/JKQMgr/UploadImages", //最大文件大小,单位是 MB maxFilesize: 5, //默认false。如果设为true,则会给文件添加上传取消和删除预览图片的链接 addRemoveLinks: true,

POJ2676 Sudoku【DFS】_海岛Blog-程序员宅基地

SudokuTime Limit: 2000MS Memory Limit: 65536KTotal Submissions: 28548 Accepted: 13016 Special JudgeDescriptionSudoku is a very simple task. A square table with 9 rows and 9 columns is divided t...

AndroidStudio使用butterknife的问题_aianzxy的博客-程序员宅基地

一、按照butterknife的官网(ButterKnife)说明配置后,执行sync now,出现了编译错误:Manifest merger failed : Attribute [email protected] value=(android.support.v4.app.CoreComponentFactory) from [com.android.supp...

AngularJS Front-End App with Cloud Storage Tutorial Part 1: Building a Minimal App in Seven Steps_weixin_30485799的博客-程序员宅基地

原文 :http://www.codeproject.com/Articles/1027709/AngularJS-Front-End-App-with-Cloud-Storage-TutoriaLearn how to build a front-end web application with minimal effort in seven steps, using the A...

推荐文章

热门文章

相关标签