Hi,欢迎来到中国嵌入式培训高端品牌 - 华清远见嵌入式学院<北京总部官网>,专注嵌入式工程师培养15年!
当前位置: > 嵌入式学院 > 嵌入式学习 > 讲师博文 > 数据结构排序算法有哪些常用的
数据结构排序算法有哪些常用的
时间:2018-01-11作者:华清远见

首先对排序有个宏观的了解, 排序的思想是这样的,将有序的记录序列(或称)按照一定的关键字,将一个序列排列成想要得到的一个新的序列。基本上现在的排序可以区分以下几类:内排序和外排序,稳定排序和不稳定排序。

内排序:整个排序过程,所有元素调到内存中进行的排序。内排序效率用比较次数来衡量。

外排序:数据量较大的情况下,需要借助外部存储设备才能完成排序。外排序用读/写外存的次数来衡量效率,块与块之间不能保证有序。

排序的性能比较最基本的是其稳定性,之后就是时间复杂度,空间复杂度了。

稳定排序:对于相的元素来说,在排序之前和之后的顺序是一样的。

不稳定排序:对于相同的元素来说,在排序之前和之后顺序发生了变化。

根据使用的实际情况,用到内排序的还是较多,所以重点讨论几种内排序。几种常见的排序算法大概有以下图中所示几种:

数据结构排序算法

那么,举几个例子,讲解下其应用的相关排序算法。

(一)冒泡排序

思想:反复扫描待排序序列,在扫描的过程中顺次比较相邻的两个元素的大小,若逆序就交换位置。第一趟,从第一个数据开始,比较相邻的两个数据,(以升序为例)如果大就交换,得到一个最大数据在末尾;然后进行第二趟,只扫描前n-1个元素,得到次大的放在倒数第二位。以此类推,最后得到升序序列。如果在扫描过程中,发现没有交换,说明已经排好序列,直接终止扫描。所以最多进行n-1趟扫描。

例:设记录key集合k={50,36,66,76,95,12,25,36},排序过程如下:

数据结构排序算法

最后排序结果为红色背景的顺序。

(二)简单选择排序

思想:第一趟时,从第一个记录开始,通过n – 1次关键字的比较,从n个记录中选出关键字最小(大)的记录,并和第一个(可以是最后一个)记录进行交换。第二趟从第二个记录开始,选择最小(大)的和第二个记录交换。以此类推,直至全部排序完毕。

例:设记录key集合k={50,36,66,76,95,12,25,36},排序过程如下:

数据结构排序算法

(三)快速排序

思想:冒泡排序一次只能消除一个逆序,为了能一次消除多个逆序,采用快速排序。以一个关键字为轴,从左从右依次与其进行对比,然后交换,第一趟结束后,可以把序列分为两个子序列,然后再分段进行快速排序,达到高效。

例:设记录的key集合k={50,36,66,76,36,12,25,95},每次以集合中第一个key为基准的快速排序过程如下:

数据结构排序算法

(四)直接插入排序

思想:最基本的插入排序,将第i个插入到前i-1个中的适当位置。

例: 设文件记录的key集合k={50,36,66,76,95,12,25,36}(考虑到对记录次key排序的情况,允许多个key相同。如此例中有2个key为36,后一个表示成36,以示区别),按直接插入排序方法对k的排序过程如下:k={50,36,66,76,95,12,25,36}

数据结构排序算法

上面呢,通过例题加图示的方式,简单的分析了其中的4个排序算法,是否理解了呢?好了,其他排序算法的分析我们以后有时间再讲。当然,理解了这种套路的话,或者你来总结一下。


发表评论

全国咨询电话:400-611-6270,双休日及节假日请致电值班手机:15010390966

在线咨询: 曹老师QQ(3337544669), 徐老师QQ(1462495461), 刘老师 QQ(3108687497)

企业培训洽谈专线:010-82600901,院校合作洽谈专线:010-82600350,在线咨询:QQ(248856300)

Copyright 2004-2018 华清远见教育集团 版权所有 ,京ICP备16055225号,京公海网安备11010802025203号