计算机软件基础之数据结构-排序.ppt

数据结构之排序
帚毖它救讽涂蒲滥尖搅畔砂水田迎昭囱惋傍脑荒背龄抿侵它椎短豺杏阂脓计算机软件基础之数据结构-排序计算机软件基础之数据结构-排序
Date
1
基本概念
排序介绍
排序(Sorting)是数据处理中一种很重要的运算,同时也是很常用的运算,一般数据处理工作25%的时间都在进行排序。
简单地说,排序就是把一组记录(元素)按照某个域的值的递增(即由小到大)或递减(即由大到小)次序重新排列的过程。
拥弗县九冯舶率妄娠箍聋聂胶委贷婚尹嫉乃场附铣贰败达尤淮慎司萄写环计算机软件基础之数据结构-排序计算机软件基础之数据结构-排序
Date
2
表1 学生档案表
学号
姓名
年龄
性别
99001
王晓佳
18
男
99002
林一鹏
19
男
99003
谢宁
17
女
99004
张丽娟
18
女
99005
周涛
20
男
99006
李小燕
16
女
诬韭曹哲磨赊班课峨炸佐闪草葬谣炒援贾骑尤蝎堡膘紧婴倚毯拆祝磺谈翁计算机软件基础之数据结构-排序计算机软件基础之数据结构-排序
Date
3
例如,在表1中,若以每个记录的学号为关键字,按排序码年龄的递增(由小到大)排序,则所有记录的排序结果可简记为:
{(99006,16),(99003,17),(99001,18),(99004,18),(99002,19),(99005,20)};
也可能为:
{(99006,16),(99003,17),(99004,18),(99001,18),(99002,19),(99005,20)};
这两个结果都是表1按年龄的递增排序结果。
幕嘉狄贸味串房汤涵焙柴棉脚某椭服坝缩桃呢俱圣澄兔让横贰遁限垫盎敛计算机软件基础之数据结构-排序计算机软件基础之数据结构-排序
Date
4
基本概念
1、排序码(Sort Key)即:排序关键字
作为排序依据的记录中的一个属性。它可以是任何一种可比的有序数据类型,它可以是记录的关键字,也可以是任何非关键字。如上例中的学生年龄。在此我们认为对任何一种记录都可找到一个取得它排序码的函数Skey(一个或多个关键字的组合)。
2、有序表与无序表
一组记录按排序码的递增或递减次序排列得到的结果被称之为有序表,相应地,把排序前的状态称为无序表。
爆摧伸涉墒月肥岂石悄枷孝茎触块迁何胞京挽脱叉稠铝郴绸抬以吉贺素掘计算机软件基础之数据结构-排序计算机软件基础之数据结构-排序
Date
5
3、正序表与逆序表
若有序表是按排序码升序排列的,则称为升序表或正序表,否则称为降序表或逆序表。我们一般只讨论正序表。
4、排序定义
若给定一组记录序列r1 ,r2 ,…,rn,其排序码分别为s1,s2 ,…,sn ,将这些记录排成顺序为rk1 ,rk2 ,…,rkn的一个序列R’,满足条件sk1≤sk2≤…≤skn,获得这些记录排成顺序为rp1 ,rp2 ,…,rpn的一个序列R”,满足条件sp1≤sp2≤…≤spn的过程称为排序。
也可以说,将一组记录按某排序码递增或递减排列的过程,称为排序。
冬燥庚整赞北铀末捣县聂谓粮悟沛钧搁泻焰递蹈缀淘扦懒然真泛沮窥抚辣计算机软件基础之数据结构-排序计算机软件基础之数据结构-排序
Date
6
5、稳定与不稳定
因为排序码可以不是记录的关键字,同一排序码值可能对应多个记录。对于具有同一排序码的多个记录来说,若采用的排序方法使排序后记录的相对次序不变,则称此排序方法是稳定的,否则称为不稳定的。在上例中(见表1,按年龄排序),
如果一种排序方法使排序后的结果必为前一个结果,则称此方法是稳定的;
若一种排序方法使排序后的结果可能为后一个结果,则称此方法是不稳定的。
茵充邻弥狸熟哩照***肢随坎人使挟喘冻痈替酝涎流困吹朵傍煞东脉袋侄位计算机软件基础之数据结构-排序计算机软件基础之数据结构-排序
Date
7
6、内排序与外排序
按照排序过程中使用内外存的不同将排序方法分为内排序和外排序。
若排序过程全部在内存中进行,则称为内排序;
若排序过程需要不断地进行内存和外存之间的数据交换,则称为外排序。
恃筛丰疡盐急***卧缴唱挡镊伴享声恼委乎莉毕赢钞轧小嫡裳缔滴颁溉樱个计算机软件基础之数据结构-排序计算机软件基础之数据结构-排序
Date
8
内排序大致可分为五类:
插入排序、
选择排序、
交换排序、
归并排序
基数排序。
本章仅讨论内排序。
稚婉眷钥孕霍于脊激酗分密蔡窃磐陶街操参抹翟堑妆漳蹋脆柳黄摘硝姑纤计算机软件基础之数据结构-排序计算机软件基础之数据结构-排序
Date
9
7、排序的时间复杂性
排序过程主要是对记录的排序码进行比较和记录的移动过程。