文档介绍：1. 排序的定义
就是把一组无序的记录按其关键字递增或递减的次序排列,便于数据的查找。
排序
排序的基本概念
2. 稳定排序和不稳定排序
对于{R1,R2,……,Rn},若有Ri=Rj, 在排序前Ri在Rj前,排序后Ri仍在Rj前,则称此排序方法是稳定的;反之为不稳定的。
1
第二章常用数据结构及其运算
排序
排序的基本概念
3. 内部排序和外部排序
内部排序:待排序记录存放在内存中进行排序。
外部排序:待排序记录数量很大,在排序过程中需访问外存。
4. 基本操作
1)对记录中关键字大小进行比较; 2)将记录从一个位置移到另一个位置。
2
第二章常用数据结构及其运算
选择排序是不断在待排序序列(无序区)中按记录关键字递增(或递减)次序选择记录,放入有序区中,逐渐扩大有序区,直到整个记录区为有序区为止。
1. 简单选择排序
1)方法:在当前无序序列中选择一个关键字最小的记录,并将它和最前端的记录交换。重复此过程,则逐渐形成由小->大的有序区。
排序
选择排序
3
第二章常用数据结构及其运算
例:设有序列:{8 3 2 5 9 1 6 },排序过程为:
i=0:[ 8 3 2 5 9 1 6 ] 6 1 3
i=1: 1 [3 2 5 9 8 6 ] 5 1 3
i=2: 1 2 [3 5 9 8 6 ] 4 0 0
i=3: 1 2 3 [5 9 8 6 ] 3 0 0
i=4: 1 2 3 5 [9 8 6 ] 2 1 3
i=5: 1 2 3 5 6 [8 9 ] 1 0 0
结果: 1 2 3 5 6 8 [9 ]
排序
选择排序
比较逻辑交换物理移动
次数次数次数
4
第二章常用数据结构及其运算
3)算法分析:第一趟排序时进行n-1次比较,第i趟排序时进行n-i次比较,总比较次数=
比较次数: n(n-1)/2
移动次数:最坏情况下为3(n-1)
时间复杂度:T(n) = O(n2)
空间复杂度为:O(1) 交换记录用
简单选择排序为不稳定排序
排序
选择排序
5
第二章常用数据结构及其运算
2. 堆排序
--在排序过程中将存放在向量中的数据看作是一棵完全二叉树,利用完全二叉树上下层结点之间的关系来完成排序。
1)堆的定义:设有序列{ k1,k2,…,kn },若满足:
则称该序列构成的完全二叉树是堆。
例:序列:{ 84 68 42 66 48 22 26 46 }构成的堆。
选择排序
排序
84
68
22
48
26
42
66
46
36
6
第二章常用数据结构及其运算
2)堆排序
①将现有的序列构成一个堆
将序列r[1:n]生成完全二叉树;
从最后一个非叶子结点开始直到根结点,逐步
调整(与其左右子树结点值进行比较,取其中
大者进行交换),则构成堆。
②输出堆顶元素,重新调整元素,构成新的堆。
重复上述过程,直到堆空为止。
排序
选择排序
7
第二章常用数据结构及其运算
例:对初始序列{46, 26, 22, 68, 48, 42, 36, 84, 66} 进行堆排序。
建堆过程:
46
26
22
68
48
42
36
84
66
46
26
22
68
48
42
36
84
66
46
26
22
84
48
42
36
68
66
46
26
22
84
48
42
36
68
66
46
26
42
84
48
22
36
68
66
46
26
42
84
48
22
36
68
66
84
68
42
66
48
22
36
26
46
84
68
42
66
48
22
36
26
46
调整为堆
46
84
42
68
48
22
36
26
66
46
84
42
68
48
22
36
26
66
8
第二章常用数据结构及其运算
排序过程:
84
68
42
66
48
22
36
26
46
84
68
42
66
48
22
36
26
46
68
66
42
46
48
22
36
26
68
66
42
46
48
22
36
26
84
66
48
42
46
26
22
36
66
48
42
46