9.4 选择排序在线视频

同学们，大家好

我是云南大学信息学院教师孔兵

这节课我们介绍选择排序

先介绍简单选择排序

简单选择排序的的思路是

通过n-i次关键字间的比较

从n-i+1个记录中选出关键字最小的记录

并和第i(1<=i<=n)个记录交换之

选择排序的方法就是为一个位置

找到排好序后应该存储在这个位置当中的记录

从i=1开始，为1号单元找记录

如果是自小到大排序

1号单元中应该是最小关键字的记录

通过n-1次比较

可以从n个记录中找到关键字最小的记录

设是j号单元的记录，如果j不等于1

记录j和记录1交换，交换后

关键字最小的记录已经在它的最终位置1号单元中

此后，循环i++等于2，为第2个位置找记录

在序列的2到n这段，通过n-2次比较

可以找到次小的一个

和2号单元的记录交换

循环直到i=n-1为止

为n-1个位置找到记录，完成排序

图1所示的序列当中有8个记录

第1趟排序，首先为第1个位置找记录

最小一个是6号单元的关键字13，把13和49交换

这样最小13号记录就已经在它的最终位置1号单元中

如图2所示，随后在2到8之间

通过比较为2号单元找记录

依次类推，后续过程就不说明了

看一下简单选择排序的实现

函数比较简单，for循环从1到n-1

为每个位置找记录

循环中用函数selectminkey在序列的i到n之间

找关键字最小的记录

并把记录的位置返回赋值给j，i不等于j时交换两个记录

看一下简单选择排序的时间效率

最好情况，如果初始序列有序，移动次数是0

最坏情况是每趟选择排序都要交换，需要移动3(n-1)次

不管初始序列如何

简单选择排序的比较次数都是n(n-1)/2

时间复杂度是O(n2)

简单选择排序移动次数较少，比较次数比较多

如何减少比较次数呢？

比较关系具有传递性，如a大于b，b大于c

已经蕴含了a大于c，不需要进行a和c的比较

通过利用比较的传递性

可以有效减少排序中比较的次数

树形选择排序就是基于这样的考虑设计的

树形选择排序，又称为锦标排序

这种方法利用比较的传递性

过程类似于体育比赛中淘汰赛的进行方式

排序思路是，首先对n个记录的关键字进行两两比较

然后在其中n/2（向上取整）个较小者之间再进行两两比较

直到选出最小关键字的记录为止

这样一个比较过程可以用一颗二叉树来描述

所以称为树形选择排序

看一个示例，有8个关键字

关键字类型为字符串，依据字典序进行比较

8个关键字构成二叉树的8个叶子

可以理解为体育比赛中的8强，随后两两比较

胜者进入双亲结点，算是4强

继续两两比较，BAO和DIAO进入决赛

BAO胜出，BAO是最终序列中的第1记录

下面要找出次小关键字，和体育比赛不同

次小关键字不一定是亚军关键字

次小关键字应该在输给冠军的关键字中确定

怎么确定呢？

寻找次小关键字的方法是

把关键字类型的最大值赋值给存有冠军的叶结点

图中用*号表示

把这个最大关键字和它兄弟结点的关键字LIU进行比较

兄弟结点是第一个输给冠军的结点

LIU胜出，进入双亲结点

LIU继续和CHEN比较

CHEN是第二个输给冠军的结点

CHEN胜出，进入双亲结点

最后CHEN和 DIAO比较

CHEN胜出，CHEN是序列中的次小关键字

下一次同样把最大值赋值给存CHEN的叶结点

进入双亲结点，最后CHEN和DIAO比较

CHEN胜出，CHEN是序列中的次小关键字

下一次同样把最大值赋值给给存CHEN的叶节点

通过这样自下而上的比较过程得到下一记录

直到所有记录8个记录都输出，完成排序

树形选择排序利用比较关系的传递性

减少了排序过程的比较次数

带来的问题是：辅助存储空间较多

n个记录需要额外n-1个空间存储分支结点

另外，每次选择都要和最大值进行一次多余的比较

下一节我们介绍树形选择排序的改进---堆排序

好同学们，今天的课就到这儿

下次课再见