中财网三蕊信号线套什么定额:9.2 排序的基本概念与分类
来源：百度文库 编辑：中财网 时间：2024/05/05 07:47:22
9.2 排序的基本概念与分类
排序是我们生活中经常会面对的问题。同学们做操时会按照从矮到高排列；老师查看上课出勤情况时，会按学生学号顺序点名；高考录取时，会按成绩总分降序依次录取等。那排序的严格定义是什么呢？
假设含有n个记录的序列为{r1,r2,……,rn}，其相应的关键字分别为{k1,k2,……, kn}，需确定1，2，……，n的一种排列p1,p2,……,pn，使其相应的关键字满足kp1≤kp2≤……≤kpn（非递减或非递增）关系，即使得序列成为一个按关键字有序的序列{rp1,rp2,……,rpn}，这样的操作就称为排序。
注意我们在排序问题中，通常将数据元素称为记录。显然我们输入的是一个记录集合，输出的也是一个记录集合，所以说，可以将排序看成是线性表的一种操作。
排序的依据是关键字之间的大小关系，那么，对同一个记录集合，针对不同的关键字进行排序，可以得到不同序列。
这里关键字ki可以是记录r的主关键字，也可以是次关键字，甚至是若干数据项的组合。比如我们某些大学为了选拔在主科上更优秀的学生，要求对所有学生的所有科目总分降序排名，并且在同样总分的情况下将语数外总分做降序排名。这就是对总分和语数外总分两个次关键字的组合排序。如图9‐2‐1所示，对于组合排序的问题，当然可以先排序总分，若总分相等的情况下，再排序语数外总分，但这是比较土的办法。我们还可以应用一个技巧来实现一次排序即完成组合排序问题，例如，把总分与语数外都当成字符串首尾连接在一起（注意语数外总分如果位数不够三位，需要在前面补零），很容易可以得到令狐冲的“753229”要小于张无忌的“753236”，于是张无忌就排在了令狐冲的前面。
（点击查看大图）图9-2-1从这个例子也可看出，多个关键字的排序最终都可以转化为单个关键字的排序，因此，我们这里主要讨论的是单个关键字的排序。