Page 129 - 高中 信息技术 选择性必修1 数据与数据结构
P. 129
5.3 排序
表5-3 超市某天商品销售的部分数据表
条形码 商品名称 单价 / 元 销售数量 单位 销售额 / 元
6947503702526 签字笔 2.3 25 支 57.5
6903388620003 牙刷 6.5 10 支 65
6911989541832 日记本 4.8 17 本 81.6
6924743910447 薯片 8.8 13 包 114.4
4891338010528 牙膏 17.5 10 盒 175
6923450605288 口香糖 1.5 37 盒 55.5
6902088702347 广东教育出版社 袋 72
洗衣粉
12
6
以表5-3中的“条形码”作为关键字排序，可以快速查找到商品的销售数据，因为每
个商品的条形码是唯一的。若想以“销售数量”来排列名次，就应把“销售数量”作为关
键字进行降序排列。待排序的元素可以是任意的数据类型，其关键字可以是整型、实型、
字符型等基本数据类型，通过排序可以构造一种新的按关键字有序排列的序列。
2．排序的分类
假定在待排序的序列中，存在多个具有相同键值的数据元素，若经过排序，这些数据
元素的相对次序仍然保持不变，则称这种排序是稳定的排序；否则，称这种排序是不稳定
的排序。例如以表5-3中的“销售数量”来排列名次：
待排序的序列：25 10 17 13 10 37 6 //给其中一个“10”加底色以区分
稳定的排序：6 10 10 13 17 25 37 //因为10还是在 10 的前面
不稳定的排序：6 10 10 13 17 25 37 //因为10已在 10 的后面
在排序过程中，可以使用内存储器，也可以使用外存储器。如果参加排序的数据元素
的数量不多，能够全部调入内存中进行排序，则称这种排序为内部排序；若参加排序的数
据元素的数量较大，需要分批调入内存中进行排序，排序后再分批存回外存储器，则称这
种排序为外部排序。
121121
21X2204.indd 121 2019/9/26 13:53:39
