几种排序算法的分析与比较--C语言
19页1、多种排序算法的分析与比较一、设计思想插入排序:首先,我们定义我们需要排序的数组,得到数组的长度。如果数组只有一个数字,那么我们直接认为它已经是排好序的,就不需要再进行调整,直接就得到了我们的结果。否则,我们从数组中的第二个元素开始遍历。然后,启动主索引,我们用curr当做我们遍历的主索引,每次主索引的开始,我们都使得要插入的位置(insertlndex)等于-1,即我们认为主索引之前的元素没有比主索引指向的元素值大的元素,那么自然主索引位置的元素不需要挪动位置。 然后,开始副索引,畐嗦引遍历所有主索引之前的排好的元素,当发现 主索引之前的某个元素比主索引指向的元素的值大时,我们就将要插入的位置 (in sertl ndex)记为第一个比主索引指向元素的位置,跳出副索弓I;否则,等待副索引自然完成。副索引遍历结束后,我们判断当前要插入的位置(insertlndex )是否等于-1,如果等于-1,说明主索引之前元素的值没有一个比主索引指向的元素的值大,那么主索引位置的元素不要挪动位 置,回到主索引,主索引向后走一位,进行下一次主索引的遍历;否则,说明主索引之前 insertlndex位置元
2、素的值比主索引指向的元素的值大,那么,我们记录当前主索引指向的元 素的值,然后将主索引之前从insertlndex位置开始的所有元素依次向后挪一位,这里注意,要从后向前一位一位挪,否则,会使得数组成为一串相同的数字。最后,将记录下的当前索引指向的元素的值放在要插入的位置(in sertl ndex )处,进行下一次主索引的遍历。继续上面的工作,最终我们就可以得到我们的排序结果。插入排序的特点在于,我们每次遍历,主索引之前的元素都是已经排好序的,我们找到比主索引指向元素的值大的第一个元素的位 置,然后将主索引指向位置的元素插入到该位置,将该位置之后一直到主索引位置的元素依次向后挪动。这样的方法,使得挪动的次数相对较多,如果对于排序数据量较大,挪动成本较高的情况时,这种排序算法显然成本较高,时间复杂度相对较差,是初等通用排序算法中的一种。选择排序:选择排序相对插入排序,是插入排序的一个优化,优化的前提是我们认为数据是比较大的,挪动数据的代价比数据比较的代价大很多,所以我们选择排序是追求少挪动,以比较次数换取挪动次数。首先,我们定义我们需要排序的数组,得到数组的长度,定义一个结果数组,用来存
3、放排好序的数组,定义一个最小值,定义一个最小值的位置。然后,进 入我们的遍历,每次进入遍历的时候我们都使得当前的最小值为9999,即认为每次最小值都是最大的数,用来进行和其他元素比较得到最小值,每次认为最小值的位置都是0,用来重新记录最小值的位置。然后,进入第二层循环,进行数值的比较,如果数组中的某个元素的值比最小值小,那么将当前的最小值设为元素的值,然后记录下来元素的位置,这样,当跳出循环体的时候,我们会得到要排序数组中的最小值,然后将最小值位置的数值设置为 9999,即我们得到了最小值之后,就让数组中的这个数成为最大值,然后将结果数组result第主索引值位置上的元素赋值为最小值,进行下一次外层循环重复上面的工作。最终我们就得到了排好序的结果数组result。选择排序的优势在于,我们挪动元素的次数很少,只是每次对要排序的数组进行整体遍历,找到其中的最小的元素,然后将改元素的值放到一个新的结果数组中去,这样大大减少了挪动的次序,即我们要排序的数组有多少元素,我们就挪动多少次,而因为每次都要对数组的所有元素进行遍历,那么比较的次数就比较多,达到了n2次,所以,我们使用选择排序的前提是,
4、认为挪动元素要比比较元素的成本高出很多的时候。他相对与插入排序,他的比较次数大于插入排序的次数,而挪动次数就很少, 元素有多少个,挪动次数就是多少个。希尔排序:首先,我们定义一个要排序的数组,然后定义一个步长的数组,该步长数组是由一组特定的数字组成的,步长数组具体得到过程我们不去考虑,是由科学家经过很长时间计算得到的,已经根据时间复杂度的要求,得到了最适合希尔排序的一组步长值以及计算步长值的公式,我们这里直接拿来使用。然后根据要排序的数组的长度,选择比长度小的最大的步长值,作为我们开始的步长。然后,进入循环遍历,外层循环由步长值决定,直到步 长为1时,我们就可以精确比较每一个数值,所以外层循环最终当步长为1时,我们就将得到排序后的结果。然后,进入内层循环,内层循环从步长那个位置开始遍历,先记录下步长值位置的数值,启动副索引j,然后比较步长值位置的元素的值与减去步长值位置元素的值, 如果减去步长值处元素的值大于步长值位置的元素的值,那么,我们将减去步长值处的元素挪到步长值位置处,将副索引指向前一个步长值处然后再判断前一步长值与再前一步长值之 间的大小关系,重复上面的工作;如果前一步长值处
《几种排序算法的分析与比较--C语言》由会员ni****g分享,可在线阅读,更多相关《几种排序算法的分析与比较--C语言》请在金锄头文库上搜索。
清洁.消毒与灭菌知识
生活中的数学(数学小论文)
固定资产加速折旧浅谈-张湖江
医院物业保洁服务方案
字母AZ单词拼写含答案
教学设计教案2
微型蒸汽机车参数
全区校长交流观摩活动有感
隧道施工安全系统管理系统规章规章制度
江苏省启东市高考物理总复习气体实验定律与理想气体状态方程理想气体状态方程课后练习(1)
高中数学公式
最新第二单元地图单元测试题商务版七上名师精心制作教学资料
上海市金山中学高二生物下学期期中试题等级06110259
xxx药品上市推广案.doc
低碳与安全
怎样养成良好习惯
柴油发电机应急操作培训资料
外研版六年级上册第四模块试题
学校后勤个人工作总结范文(二篇).doc
上海市新污染物治理产品项目可行性报告_参考模板
2023-08-10 6页
2022-11-28 8页
2023-09-16 4页
2022-12-03 4页
2022-10-27 3页
2023-02-22 27页
2023-03-03 6页
2022-09-25 5页
2023-03-13 5页
2023-06-08 14页