计算机学院 软件工程系


Gap的取法有多种。最初 shell 提出取 gap = n/2，gap = gap/2，直到gap = 1。knuth 提出取 gap = gap/3 +1。还有人提出都取 奇数为好，也有人提出各 gap 互质为好。 对特定的待排序对象序列，可以准确地估算 排序码的比较次数和对象移动次数。
计算机学院 软件工程系
例：关键字序列 T=(49，38，65，97, 76, 13, 27, 49*，55,
04），请写出希尔排序的具体实现过程。 r[i] 0 1 2 3 4 5 6 初态：
第 1趟 第 2趟 第 3趟
gap
7
8
9 04
04 76 76 76 97
49
49 13 13 13 04
优点：每趟结束时，不仅能冒出一个最小值 (最 大值)到最前(后)面位置，还能同时部分理顺其 他元素；一旦下趟没有交换发生，还可以提前结 束排序。
20

计算机学院 软件工程系
例如: 2 1 5
5 3 2 1 2 5 3 3 1
5 1
7 9
9 8 7
9 8
i=n
i=5 i=6
21
计算机学院 软件工程系
有序序列r[1..i]
无序序列 r[i+1..n]
7
计算机学院 软件工程系
直接插入排序 (Insert Sort)
• 基本思想是 : 当插入第i (i 1) 个对象时, 前面 的V[0], V[1], …, V[i-1]已经排好序。这时, 用 V[i]的排序码与V[i-1], V[i-2], …的排序码顺序 进行比较, 找到插入位臵即将V[i]插入, 原来位 臵上的对象向后顺移。 • 插入过程分为两步:
基本思想：因为 R[1..i-1] 是一个按关键字有
序的有序序列，则可以利用折半查找实现“在
R[1..i-1]中查找R[i]的插入位置”，如此实现
的插入排序为折半插入排序。
12
计算机学院 软件工程系
例如:
插入 位置
i
L.r 14 36 49 52 80 58 61 23 97 75
low high low low high m m
讨论：若记录是链表结构，折半插入排序可行吗？ 链表无法“折半”！
15
计算机学院 软件工程系
希尔排序 (Shell Sort)

希尔排序方法又称为缩小增量排序。 该方法的基本思想是 :对待排记录序列先作 “宏观”调整，再作“微观”调整。
每一趟排序：将待排序序列分成若干子序列。子序 列的构成不是简单地“逐段分割”，而是将相隔某 个增量的记录组成一个子序列，然后对每个子序列 进行插入排序。 下一趟开始前让增量逐趟缩短（例如依次取5,3,1）， 直到增量＝1,用直接插入法做微观调整。 16
38
38 27 27 04 04 13
65
49* 65 49* 49* 27
97
97 55 55 38 38
76
76 04 27 04 49* 27
13
13 49 49 49
27 49* 55
27 38 38 55 55 49* 65 65 65 55 97 97 97 76
5 3 1
分析：开始时dk 的值较大，子序列中的对象较少，排序速度较 快,让关键字值小的元素能很快前移，使序列基本有序； 随着排序进展，dk 值逐渐变小，子序列中对象个数逐渐 变多，由于前面工作的基础，大多数对象已基本有序， 17 只做局部调整即可，所以排序速度仍然很快。
9
计算机学院 软件工程系
直接插入排序的算法分析



设待排序对象个数为currentSize = n, 则该算 法的主程序执行n-1趟。 排序码比较次数和对象移动次数与对象排序 码的初始排列有关。 最好情况下（关键字在记录序列中顺序有 序）, 每趟只需与前面有序对象序列的最后 一个对象比较1次, 移动2次对象, 总的排序 码 比较次数为 n-1, 对象移动次数为2(n-1) 。
3
计算机学院 软件工程系
• 排序的目的：便于查找 • 内排序与外排序: 内排序是指在排序期 间数据对象全部存放在内存的排序；外 排序是指在排序期间全部对象个数太多， 不能同时存放在内存，必须根据排序过 程的要求，不断在内、外存之间移动的 排序。
4
计算机学院 软件工程系
• 排序算法好坏的衡量： 1）时间效率
25
计算机学院 软件工程系
例：关键字序列 T=(21，25，49，25*，16，08），快 速排序的算法步骤:
初态： 第1趟： 第2趟：
21， 25， 49， 25*，16， 08
( 08，16, ) 21 ，( 25* ，25，49 ) 08， (16)，21， 25* ，(25，49) 08， 16， 21，25* ， 25，(49)
再如:
插入 位置
m
i
L.r 14 36 49 52 58 61 80 23 97 75
low high low high m m m high
13
计算机学院 软件工程系


折半搜索比顺序搜索查找快, 所以折半插入 排序就平均性能来说比直接插入排序要快。 它所需的排序码比较次数与待排序对象序列 的初始排列无关, 仅依赖于对象个数。在插 入第 i 个对象时, 需要经过 log2i +1 次排序 码比较, 才能确定它应插入的位臵。因此, 将 n 个对象(为推导方便, 设为 n=2k )用折半插入 排序所进行的排序码比较次数为： n 1 log2 i 1 n log2 n
初态：
暂 49 25 25* 16 存 08 0
16 21 08 1
i=1
25 16 21 2
i=2
49 21 25* 25 3
i=3
49 25* 25 4
i=4
49 25* 16 5
i=5
49 08 6
i=6
完成!
考虑:若记录是链表结构,插入排序是否可行? 直接插入不仅可行，而且还无需移动元素，时 间效率更高！
6
计算机学院 软件工程系
插入排序 (Insert Sorting)
基本方法是 : 每步将一个待排序的对象, 按 其排序码大小, 插入到前面已经排好序的一组 对象的适当位臵上, 直到对象全部插入为止。
共做n趟排序，第i趟排序的过程如下: 有序序列r[1..i-1] r[i] 无序序列 r[i..n]
18
计算机学院 软件工程系
交换排序 ( Exchange Sort )
基本思想是两两比较待排序对象的排序码, 如果发生逆序(即排列顺序与排序后的次序 正好相反)，则交换之。直到所有对象都排 好序为止。
19
计算机学院 软件工程系
起泡排序 (Bubble Sort)

基本方法是：设待排序对象序列中的对象 个数为 n。最多作 n-1 趟，i = 1, 2, , n-1 。 在第 i 趟中从后向前，j = n-1, n-2, , i， 顺次两两比较V[j-1].key和V[j].key。如果发 生逆序，则交换V[j-1]和V[j]。
10
计算机学院 软件工程系

最坏情况下 （关键字在记录序列中逆序有 序）, 第 i 趟时第 i 个对象必须与前面 i 个对 象都做排序码比较, 并且每做1次比较就要做 1 次数据移动。则总排序码比较次数 KCN 和 对象移动次数RMN分别为
KCN i n(n 1) / 2 n / 2,
1 KCN ( n i ) n( n 1) 2 i 1 n 1 3 RMN 3 ( n i ) n( n 1) 2 i 1
n 1
23
计算机学院 软件工程系
快速排序 (Quick Sort)

基本思想是任取待排序对象序列中的某个对 象 (例如取第一个对象) 作为基准, 按照该对 象的排序码大小, 将整个对象序列划分为左 右两个子序列：

折半插入排序是一个稳定的排序方法。
14
i 1
计算机学院 软件工程系


当 n 较大时, 总排序码比较次数比直接插入 排序的最坏情况要好得多, 但比其最好情况 要差。 在对象的初始排列已经按排序码排好序或 接近有序时, 直接插入排序比折半插入排序 执行的排序码比较次数要少。折半插入排 序的对象移动次数与直接插入排序相同 , 依 赖于对象的初始排列。
第3趟：
26
计算机学院 软件工程系

算法quicksort是一个递归的算法, 其递归树 如图所示。
21
08
16
25*
25
49
那么：一趟排序过程如何实现?
27
计算机学院 软件工程系
例：快速排序算法的一趟实现过程:
初态：
21， 25， 49， 25*，16， 08
第1趟： (08，16)，21，(25*，25 ，49) 0 1 2 3 4 5
计算机学院 软件工程系
概述 插入排序 交换排序 选择排序 归并排序 基数排序 外排序

1
计算机学院 软件工程系
概述


数据表(datalist): 它是待排序数据对象的有限 集合。 关键码 (key): 通常数据对象有多个属性域 , 即多个数据成员组成 , 其中有一个属性域可 用来区分对象 , 作为排序依据。该域即为关 键码。每个数据表用哪个属性域作为关键码， 要视具体的应用需要而定。

2）空间效率
3）稳定性
排序的时间开销: 排序的时间开销是衡量算法好 坏的最重要的标志。排序的时间开销可用算法执 行中的数据比较次数与数据移动次数来衡量。 算法运行时间代价的大略估算一般都按平均情况 进行估算。对于那些受对象排序码序列初始排列 及对象个数影响较大的，需要按最好情况和最坏 情况进行估算。