第9章内排序2

8
9.4.1 直接选择排序 7、直接选择排序的算法
void SelectSort ( elemtype L[],int n )
{
for ( i = 1; i < n; i++ ) /*总共进行n-1次排序*/
{ k = i;
for ( j = i+1; j <n; j++)
/*在剩余记录序列中选择最小的记录*/
ri-1 ri … rk … rn
交换 最小记录
ri-1 ri ri+1… ri … rn
常用的选择排序算法： （1）直接选择排序 （2）堆排序
3
9.4 选择排序
9.4.1 直接选择排序
1、基本思想 每经过一趟比较就找出一个最小值，与待排序列最前面的位
置互换. 2、优点：实现简单 3、缺点：每趟只能确定一个元素，表长为n时需要n-1趟 4、前提：顺序存储结构
4
9.4.1 直接选择排序
5、直接选择排序的过程
初始 21
0
i = 1 21
25
49
25*
16
08
12345
最小者 08
25
49 25*
16
交换21,08 08
最小者 16
i=2
08
25
49 25* 16
21 交换25,16
最小者 21
i=3
08
16
49 25* 25
21 交换49,21
5
9.4.1 直接选择排序
过程中关键码最小的记录位置。
21
25
49
28
16 08
index
index index
7
9.4.1 直接选择排序
需解决的关键问题?
⑵如何确定最小记录交换后的最终位置？
解决方法：
第i趟简单选择排序的待排序区间是r[i] ~ r[n]，则r[i]
是无序区第一个记录，所以，将index所记载的关键 码最小的记录与r[i]交换。
√ （大根堆） （大顶堆） （最大堆）
15
9.4.2 堆排序 2、堆排序的基本思想
将原始记录序列建成一个堆，称之为初始堆，并 输出堆顶元素；调整剩余的记录序列，使之成为一个新 堆，再输出堆顶元素；如此反复，当堆中只有一个元素 时，整个序列的排序结束，输出的序列就是原始序列的 有序排列。
主要要解决的关键问题： 1、如何将原始记录序列建成一个堆，即新建堆? 2、如何处理堆顶记录？ 3、如何将剩余记录调整成一个新堆, 即重建堆？
16
9.4.2 堆排序
为什么？
关键问题1：如何新建堆？
步骤：首先将一个待排序的记录序列按原始顺序建成一个完全 二叉树。从最后一个非终端结点开始往前逐步调整，使 每个双亲都大于（或小于）它的子女，直到根结点为止。
例：关键字序列T= (21，25，49，25*，16，08），请建大根堆。
完全二叉树的最后一个非终端结
14
9.4.2 堆排序 例：有序列T1=（08, 25, 49, 46, 58, 67）和序列T2=（91, 85, 76, 66, 58, 67, 55）,判断它们是否 “堆”？
1
08
2
3
25
49
4
56
46 58 67
1
91
2
3
85
76
4
56 7
66 58 67 55
√ （小根堆） （小顶堆） （最小堆）
简单选择排序的时间复杂度为O(n2)。
空间性能：需一个辅助空间。 稳定性：是一种不稳定的排序算法。
11
9.4 选择排序
9.4.2 堆排序--直接选择排序法的改进算法
改进的着眼点：如何减少关键码间的比较次数。若 能利用每趟比较后的结果，也就是在找出键值最小 记录的同时，也找出键值较小的记录，则可减少后 面的选择中所用的比较次数，从而提高整个排序过 程的效率。
1
点编号必为n/2 ！！（性质5）
4291
2
25
3
4291
i=3: 49大于08，不必调整； i=2: 25大于25*和16，也不必调整；
4
56
i=1: 21小于25和49，要调整！
25* 16 08
而且21还应当向下比较！！ 17
9.4.2 堆排序 关键问题1：如何新建堆？
算法描述： for (i=n/2; i>=1; i--)
1 2345 1 2345 1 2345 1 2 345 1 2345
10
9.4.1 直接选择排序
移动次数： 最好情况（正序）：0次
最坏情况：3(n-1)次
比较次数：
n-1
（n
i =1
-i）=
12n(n
-1)
=O(n2 )
45 231 15234 1 2 53 4 1 2 35 4 1 2 3 45
减少关键码间的比较次数
查找最小值的同时，找出较小值
12
9.4.2 堆排序
1. 什么是堆？
堆的定义：设有n个数据元素的序列 k1，k2，…，kn，当且 仅当满足下述关系之一时，称之为堆。
ki ≤ k2i 或者 ki ≤ k2i+1
ki ≥ k2i ki ≥ k2i+1
i=1, 2,… n/2
解释：如果让满足以上条件的元素序列 （k1，k2，…，kn）顺 次排成一棵完全二叉树，则此树的特点是：
树中所有结点的值均大于（或小于）其左右孩子，此树的根 结点（即堆顶）必最大（或最小）。
13
9.4.2 堆排序 堆和序列的关系
50
38
45
32
36 40 28
采用顺序存储
20 18 28
1 2 3 4 5 6 7 8 9 10
50 38 45 32 36 40 28 20 18 28
将堆用顺序存储结构来存储，则堆对应一组序列。
1
主要内容
9.1 排序的基本概念 9.2 插入排序 9.3 交换排序 9.4 选择排序 9.5 归并排序 9.6 分配排序 9.7 性能比较
2
9.4 选择排序
选择排序的主要操作是选择，其主要思想是：每趟排序在当 前待排序序列中选出关键码最小的记录，添加到有序序列中。
有序序列
无序序列
r1 r2 …… r1 r2 ……
Βιβλιοθήκη Baidu
{ if ( r[j] < r[k] )
k = j;
} ? /* k记录当前最小排序码的位置*/
if ( k != i ) {
Swap ( r[i], r[k] );
} ? /*与第 i 个位置的元素对换*/
}
9
9.4.1 直接选择排序 8、直接选择排序算法的性能分析
移动次数： 最好情况（正序）：0次
i=4
08 0
i=5
08
最小者 25*
16
21
25*
25
49 无交换
12345
最小者 25
16
21
25*
25
49 无交换
结果
08
16
21
25* 25
49
各趟排序后的结果
6
9.4.1 直接选择排序
需解决的关键问题?
⑴如何在无序区中记录关键码最小的记录？
解决方法： 设置一个整型变量index，用于记录在一趟比较的