文档介绍：数据结构
Data Structures
张 凯
计算机学院 软件工程系
2011年3月12日
1
第10章 内部排序
选择排序 (直接排序、堆排序)
概述
插入排序 (直接排序、折半排序、希尔排序)
交换排序 (冒泡排序、快速排序)
归并排序
基数排序
2
选择排序
§ 选择排序
基本思想：
第i趟在n-i+1(i=1,2,…,n-1)个记录中选取关键字最小的记录作为有序序列中的第i个记录。
3
简单选择排序
§ 选择排序
排序过程：
首先通过 n –1 次关键字比较，从 n 个记录中找出关键字最小的记录，将它与第一个记录交换。
再通过 n –2 次比较，从剩余的 n –1 个记录中找出关键字次小的记录，将它与第二个记录交换。
重复上述操作，共进行 n –1 趟排序后，排序结束。
4
简单选择排序
§ 选择排序
例：
初始： [ 49 38 65 97 76 13 27 ]
j
j
j
j
j
j
k
i =1
13
49
一趟： 13 [38 65 97 76 49 27 ]
i =2
二趟： 13 27 [65 97 76 49 38 ]
三趟： 13 27 38 [97 76 49 65 ]
四趟： 13 27 38 49 [76 97 65 ]
五趟： 13 27 38 49 65 [97 76 ]
六趟： 13 27 38 49 65 76 [97 ]
排序结束：六趟： 13 27 38 49 65 76 97
k
k
i =6
i =3
i =4
i =5
比较次数
n - 1
n - 2
n - 6
5
简单选择排序算法描述
§ 选择排序
void SelectSort (SqList &L) { // 对顺序表 L 作简单选择排序
for (i = 1; i < ; ++ i) {
k = i;
for ( j = i+1; j <= n; j++) if ([j].key < [k].key) k = j;
if (i != k) [i]←→[k]; // 与第 i 个记录交换
}
} // SelectSort
6
简单选择排序算法分析
§ 选择排序
由于存在着不相邻元素之间的互换，因此，简单选择排序是“不稳定的” 。
算法实现共需要进行n-1 次选择，每次选择需要进行n-i次比较(1≤i≤n-1)，而每次交换最多需3次移动，因此，总的比较次数 C = n(n-1)/2，总的移动次数 M = 3(n-1)。故其时间复杂度为O(n2)。
空间效率：O(1)——交换时用到一个暂存单元
7
树形选择排序 (又称锦标赛排序 )
§ 选择排序
基本思想：与体育比赛时的淘汰赛类似。
首先对 n 个记录的关键字进行两两比较，得到 n/2 个优胜者(关键字小者)，作为第一步比较的结果保留下来。然后在这 n/2 个较小者之间再进行两两比较，…，如此重复，直到选出最小关键字的记录为止。
例：关键字序列T= （21，25，49，25*，16，08，63），请给出锦标赛排序的具体实现过程。
8
08
Winner (胜者)
21
08
08
63
25*
21
21
25
49
25*
16
08
63
r[1]
注：为便于自动处理，建议每个记录多开两个特殊分量：
key
otherinfo