资源描述：
《对某种排序算法是“稳定的”或“不稳定的”的浅析.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、14..第卷第期辽宁师专学报VoNo41哭旧年12月倒叮因ofLiOa毗gn毛汾cherC目】LC1哭旧eg晚“”对某种排序算法是稳定的“”或不稳定的的浅析冯晓辉(营口师专营口115(X)3,摘要排序是(数据结构》这门学科所包括的一项重要内容排序主要是针对文件而言,,,有些文件存在多个具有相同排序码的记录对于这样的文件按着不同的排序算法进行排序会得.“”“”,,到不同的排序结果排序算法可以分为稳定的和不稳定的两种应正确理解这两个概念.掌握不同的排序算法的基本思想关键词排序文件记录排序码稳定的不稳定的在学习(数据
2、结构》时,对于某种排序算法是稳定的或不稳定的,有些学生不太理..,,解这里作一下浅显的分析要学好这方面的知识必须掌握好以下几个环节1问题的提出.《数据结构》是计算机专业学生的必修课之一,它所包含的一项重要内容就是排序排序.主要是针对文件而言的文件是一些记录(结点)的汇集,其中每个记录由一个或多个数据项..(字段)组成排序码是结点中一个(或多个)字段,该字段的值作为排序运算中的依据所.谓排序就是将记录按排序码不增或不减的次序排列起来在一个文件中,若存在多个具有相同,,排序码的记录那么按着这个排序码排序这些记录谁排
3、在前谁排在后呢?这就涉及到某种排.:序算法是稳定的或不稳定的概念下面是一个由八条记录组成的文件记录号编号姓名性别年龄职称l以X)l李南女40工程师2以叉)2王玲女35助理工程师30以〕3刘洋女40工程师4以叉又马红女50工程师5以刃5白玉海男28助理工程师6以卫拓李南女45工程师7仪刃7张一峰男48工程师8以x)8赵华男59高级工程师现在以年龄作为排序码来排序(以下同,并且排序是由小到大进行的),李南和刘洋都是40.,岁排序后谁在前谁在后呢?这就要看给这个文件排序时所用的算法所谓算法就是对特定的.问题求解过程的
4、描述使用不同的排序算法,就会使排序后具有相同排序码的记录的排序结果有所不同.~收稿日期1哭珍e1仓一30辽宁师专学报1燮剩〕年第4期如果在待排序的文件中,存在多个具有相同排序码的记录,经过排序后,这些记录的相对.,“”,“”次序仍然保持不变这种排序算法称为稳定的否则称为不稳定的,“”“”2通过学习各种排序算法理解稳定的和不稳定的这两个概念,、:在《数据结构》教材中一般都包括这样几种排序方法直接插人排序二分法插人排、、、,序hsen排序直接选择排序起泡排序和快速排序(当然还包括其它的一些排序方法)并.,且把这些排
5、序方法都进行了分类这里仅就上述六种排序方法作一比较正确理解某种排序算法是稳定的或不稳定的概念..要正确理解某种排序算法是稳定的或不稳定的概念,必须掌握这种排序方法的基本思想.不同的排序方法,排序过程是不同的对于直接插人排序,它的基本思想是将一个记录插人到.,、已排好序的有序表中从而得到一个新的记录数增1的有序表排序过程主要是找插人位.置当待插记录的排序码与某个记录的排序码相同时,采取的方法是将该记录后面的记录依次..后移,使待插记录放在该记录的后面算法就是依据这个思想来完成的用这种排序算法对前,:面的文件进行排
6、序排序结果是记录号编号姓名性别年龄职称5以X)5白玉海男28助理工程师2以X)2王玲女35助理工程师1仪X)l李南女40工程师3〔犯叼3刘洋女40工程师6(XX拓李南女45工程师7X(X)7张一峰男48工程师4(X)叫马红女50工程师80汉〕8赵华男59高级工程师.,,这种排序方法是稳定的换成其它任何文件用这种排序算法对于具有相同排序码的记录都会得到排序前.和排序后相对不变的排列次序,:,s:7、录放在一组中在各组内进行排序然后取整数d2重.,!二1复上述分组和排序工作直到取d即所有记录放在一组中排序为止用这种排序方法对前,:面的文件进行排序结果为5仪心5白玉海男28助理工程师2(X刃2王玲女35助理工程师3以⋯X)3刘洋女40工程师1(X心l李南女40工程师6(X巧李南女45工程师7以洲)7张一峰男48工程师4《XX岭马红女50工程师8以x)8赵华男59高级工程师这种排序方法是不稳定的.“”“”3对于某种排序算法是稳定的或不稳定的这两个概念的深化对于某种排序算法是稳定的或不稳定的这两个概念的理解,重要
8、的是看具有相同排序码的.记录比较后,它们所排的次序,这个次序一般情况下依赖于算法中用到的判断条件对于直接插人排序、二分法插人排序,判断条件都是当后面记录的排序码小于前面记录的排序码时,再“”“”冯晓辉对某种排序算法是德定的或不德定的的浅析.继续往前面找插人位置换句话说,就是在比较时,一旦出现相等情况,则采取以先输入的为.,,,主的方法排在前面的仍就排在前面对于起泡排序也是如此比较两个记
