Rp1, Rp2, Rp3, Rp4, Rp5, Rp6, Rp7, Rp8
一般情况下，假设含 n 个记录的序列为{ R1, R2, …, Rn }， 其相应的关键字序列为 { K1, K2, …, Kn }
这些关键字相互之间可以进行比较，即在它们之间存在着这
样一个关系(在次讨论升序) ：
Kp1≤Kp2≤…≤Kpn
数据结构-排序.
第1页
概念
排序：将数据元素的一个任意序列，重新排列成一个按关键
字有序的序列。
R1, R2, R3, R4, R5, R6, R7, R8
例：将关键字序列：52, 49, 80, 36, 14, 58, 61, 23
K1, K2, K3, K4, K5, K6, K7, K8
Kp1 ≤Kp2 ≤Kp3 ≤Kp4 ≤Kp5 ≤ Kp6 ≤Kp7 ≤Kp8 调整为：14, 23, 36, 49, 52, 58, 61 , 80
54321
第9页
希尔排序（缩小增量排序）
基本思想：对待排序列先作“宏观”调整，再作“微观”调 整。排序过程：先取一个正整数 d1 < n，把所有相隔 d1 的记录放 在一组内，组内进行直接插入排序；然后取 d2 < d1，重复上述分 组和排序操作；直至 di = 1，即所有记录放进一个组中排序为止。 其中 di 称为增量。
第3页
➢ 内部排序和外部排序
若整个排序过程不需要访问外存便能完成，则称此类排序问 题为内部排序；
反之，若参加排序的记录数量很大，整个序列的排序过程不 可能在内存中完成，则称此类排序问题为外部排序(本章不讨论) 。
➢ 内部排序的方法内部排序的过ຫໍສະໝຸດ 是一个逐步扩大记录的有序序列的过程。
有序序列区 有序序列区
无序序列区 经过一趟排序
无序序列区
第4页
依次将无序子序列中的一
个记录“插入”到有 序序列中，
排序方法分类：
从而增加记录 的有序子序列的
通长过度“。交换”无序序列中的记录从而
基于不同的“得扩到大其从”中记有关录序键的序字无列最序长小子度序或的列最方中大法“的，记选内录择部，”排并序
方法1大)、致插可入分排下序列将加关加加：或序几它记键入记直两子种录字到录加基接个序通类的最有的入数插以列过型有小序有到排入上，“：序子序有或排的逐归子序子序最是序记步并序列序子大一、录增”列列序种的中折有加两的的列基记，半个长长于中录以插度度多，，此入。。以并方排此将法序方它增、法希增尔排序
按此固有关系将上式记录序列重新排列为{ Rp1, Rp2, …, Rpn } 的操作称作排序。
第2页
若 Ki 为记录 Ri 的主关键字，则排序结果惟一。 若 Ki 为记录 Ri 的次关键字，则排序结果可以不惟一（因为 会有相同的关键字）。
例：设排序前的关键字序列为：52, 49, 80, 36, 14, 58, 36, 23 若排序后的关键字序列为：14, 23, 36, 36, 49, 52, 58, 80， 则排序方法是稳定的。 若排序后的关键字序列为：14, 23, 36, 36, 49, 52, 58, 80， 则排序方法是不稳定的。
移动次数：0
最坏的情况：待排序记录按关键字从大到小排列（逆序）
比较次数：
n (n2)(n1) i
i2
2
移动次数：
n
(n4)(n1)
(i1)
i2
2
一般情况：待排序记录是随机的，取平均值。
比较次数和移动次数均约为： n 2
时间复杂度： T(n)=O(n²)
4
直接插入排序是稳定排序
空间复杂度：S(n)=O(1)
时实L.现r[ 记j +录1]向=后L.移r[动j ]；; // 记录后移
38 4插L9.入r[ jR6+5[i1]];= L97.r[0];76 //1插3入到2正7 确位49置
i =5
76 38 } 49 65 76 97 13 27 49
} // InsertSort
7趟
i =6
13 13 38 49 65 76 97 27 4排9 序
排序i =过7程：先将27序列13中第271 个3记8 录看49成是65一个7有6 序子97序列49，
然后i =从8第 2 个记49录开13始，2逐7 个3进8 行插49入，49直至6整5 个序76列有97序。
第8页
算法评价
最好的情况：待排序记录按关键字从小到大排列（正序）
n
比较次数： 1 n 1 i2
例：第一趟分组，设 d1 = 5 49 38 65 97 76 13 27 499 5555 0044
第一二趟希分尔组排，序设 d2 = 3 13 27 49 55 04 49 38 65 97 76
4398 43在L98.rR[0[6]1.=5. iL-1.r]中[9i]7;查找7R6[i/]/ 复的1制插3 为入监位27视置哨; 49
对L.于r[i在] =查L找.r[过i -程1];中找到的那些关键字
38 4不f9or小(于j6=5Ri [-i]2.;k9Le7y.r的[0记]7.k6录ey，<1在L3.查r[ 找j2].的7ke同y; 4-9- j )
第7页
直接插入排序
R0 初始状态
i =2
38
i =3
i =4
void InsertSort ( SqList &L ) {
R/f/1o对r (顺Ri 序=2 2表; RiL<3=作L直.lRe接n4g插th入;R+排5+序i )。R6
R7
1趟 R排8 序 2趟
49 if 3(L8.r[i]6.k5ey < L9.7r[i -17].6key)1{3 27 4排9 序
2)、交换排序关：记键冒录字泡有排排序序序序的、列思快的想速长，排度将序。单关
键字按基数分成 “多关键字”
3)、选择排序进：行简排单序选的择方排法序。、堆排序
＊ 4)、归并排序：2-路归并排序
＊ 5)、基数排序
第5页
目录
1
排序的基本概念
32
插入类排序
3
交换类排序
34
选择类排序
35
归并排序
36
小结
第6页
简单排序方法
插入排序
一趟直接插入排序的基本思想：
有序序列 R[1 .. i -1]
无序序列 R[i .. n]
R[i]
有序序列 R[1 .. i]
无序序列 R[i +1 .. n]
实现“一趟插入排序”可分三步进行：
1．在 有序区 中查找 R[i] 的插入位置， 2．记录后移一个位置； 3．将 R[i] 插入（复制）到 相应 的位置上。