计算机课件第八章 排序

排序的定义

排序的功能是将一个数据元素（记录）的任

意序列，重新排列成一个按关键字有序的

序列。

★¥

*

2

排序的分类

•按待排序记录所在位置

内部排序：待排序记录存放在内存

夕卜部排序：排序过程中需对外存进行访问的

排序

•按排序依据原则

插入排序：直接插入排序、折半插入排序、

希尔排序

交换排序：冒泡排序、快速排序

选择排序：前单选择排序、堆排序去.

归并排序：2-路归并排序★

3

排序的基本操作

•比较两个关键字大小

将记录从一个位置移动到另一个位置

★¥

*

4

排序对象的数据类型

定义待排序的记录的数据类型为:

typedefstruct

{intkey;

elemtypedata;

}redtype;

redtyper[n];

★¥

5

插入排序

基本思想：每步将一个待排序的记录，按其

关键字值的大小插入到前面已经排序的文件

中适当的位置上，直到全部插完为止。

★»

3

★

插入排序直接插入排序

例i=l(49386597761327比较次数移动次数

____I

i=238(3849)659776132721

i=3(384965)9776132710

i=4(38496597)76132710

i=5(3849657697)132721.

i=6(133849657697)彳765

i=7(132738496576976

jj'Jj'j'j'

排序结果：(13273849657697)

8

直接插入排序算法算法8.Ltxt

(1)设置监视哨r[0],将待插入记录的

值赋给r[0];

(2)设置开始查找的位置j;

(3)在数组中进行搜索，搜索中将第j个

记录后移，直至r[0].key>r[j].key为止

(4)将r[0]插入在r[j+l]的位置上

■

9

直接插入排序算法分析

按平均比较次数计算，将n个记录进行直接插入排序所

需的平均比较次数为：

n2

i(H+2)(H-1)“2+〃一2n

Sin——

i=2乙444

直接插入排序的时间复杂度为2

0(n)o

空间复杂度为0(1)

★¥

直接插入排序是一种稳定的排序方法。

★

10

插入排序希尔排序

希尔排序的作法是：选定第一个增量

dl<n,把全部记录按此值从第一个记录

起进行分组，所有相距为dl的记录作为

一组，先在各组内进行插入排序，然后

减小间隔，取第二个增量d2〈dl,重复上

述分组和排序过程，直至增量值di=l为

止，即所有的记录放在同一组内排序。

■

11

例初始：4938659776132748554

取dl=5

—分2目;4。a父6s。77A14974554

一趟排序：5549776

取d2=3

二趟分组：〔1I7,

二趟排序：

取d3=l

三趟分组：1327485544938659776

1―：；

三趟排序：4132738484955657697/

12

匐

插入排序希尔排序算法算法8.2.txt

1）外循环以各种不同的间隔距离d进行排序，直

到d==l为止；

2）第二重循环是在某一个d值下对各组进行排序，

若在某个d值下发生了记录的交换，则需继续

第三重循环循环，直至各组内均无记录的交换

为止。即各组内已完成排序任务;

3）第三重循环是从第一个记录开始，按某个d值

为间距进行组内比较。若有逆序，则进行交换。

★★

■

13

希尔排序笋法分析

主要特点是每一趟以不同的增量进行插入

排序。当d较大时，被移动的记录是跳跃

式进行的。到最后一趟排序时(d=l),许

多记录已经有序，不需要多少移动，所以

能提高了排序的速度。

希尔排序是不稳定的排序方法。

JT14

交换排序

交换排序是通过两两比较待排序记录的

关键值，交换不满足顺序的那些偶对，直到

全部满足为止。

★¥

15

*

交换排序

算法&3.txt

1.将第一个记录的关键字与第二个记录的关

键字进行比较，若为逆序

r[1].key>r[2].key,则交换；然后比较第

二个记录与第三个记录；依次类推，直至

第nT个记录和第n个记录比较为止-----第

一趟冒泡排序，结果关键字最大的记录被

安置在最后一个记录上。

2.对前nT个记录进行第二趟冒泡排序★约臀

使关键字次大的记录被安置在军T个记录

位置。

交换排序

38

例3838383313

1327

4949492727

U

65653030

2730第

761338六

3038第

27

趟

五

13274949第

30

趟

2730四

65第

65

趟

3076二

76第

趟

97初

97第

二

一

始

趟

趟

关

键

字

7

冒泡排序算法分析

由上述算法可见，当初始序列中记录已按关

键字次序排好序，则只需要进行一趟排序，

在排序过程中只需要进行nT次比较，记录移

动次数为0；反之，若初始序列中记录按逆序

排列，若待排序的序列有n个记录，最多进行

nT趟排序，最大比较次数为

n—\n(n—1)n2

zs—)=-----x--

i=l22

交换记录时移动记录的次数也约为3n2/2次，故费,

的时间复杂度为0(/)o冒泡排序是稳定的小牛

18

对r[s...中记录进行一趟快速相、序,附设两

个指针i和j,设枢轴记录rp=r[s],x=rp.key

♦初始时令i=s,j=t

♦首先从j所指位置向前搜索第一个关键

字小于x的记录，并和rp交换

♦再从i所指位置起向后搜索，找到第一

个关键字大于x的记录，和rp交换

♦重复上述两步，直至i=j为止

♦再分别对两个子序列进行快速排好，*

直到每个子序列只含有一个记军为止

20

X

11

初始关键字:2738134976976550

tT

ftt•*tt

ii1项jJJj

完成一趟排序：(273813)49(76976550)

分别进行快速排序：(13)38)49(5065)76(97)

快速排序结束：1338495065

21

4.txt

1)确定第一个记录为基准记录中],先从j所指示的位

置起向前扫描，当中].key>r[j].key时，交换中].key

和r5.key,使关键字值比基准记录的关键字值小的

记录交琉到前面；

2)从i所指示的位置起向后扫描，直到r[t].key〈r[i].key,

交换巾].key和r[i].key,使关键字值比基准记录的关

键字值大的记录交换到后面；

3)重复（1）和（2）,直至i=j为止完成一趟排序；

4)只要t<w,重复（1）至（3）分别对基准记录两边

的部分进行排序。

■

22

快速排序的排序算法分析

快速排序平均时间复杂度为

0(nlog2n)o

最坏情况下时间复杂度为0(n2),快速排序所

需的比较次数反而最多。

快速排序法不稳定。

快速排序需要一个栈空间来实现递归。栈的

最大深度为所需栈空间为

Llog2nJ+1,

最坏情况下，递归深度为所需

0(log2n)on,

栈空间为0(n)。去、

23

选择排序是指每次从待排序的记录中

选出关键字值最小（或最大）的记录，顺

序放在已排序的有序序列中，直到全部排

完。选择排序主要包括简单选择排序和堆

排序两种。

■

24

选择排序-----简单选择排序

♦首先通过nT次关键字比较，从

n个记录中找出关键字最小的记录，

将它与第一个记录交换

♦再通过n-2次比较，从剩余的n-

1个记录中找出关键字次小的记录，

将它与第二个记录交换

♦重复上述操作，共进行nT趟排

序后，排序结束

★¥

■

25

kkk

III

例i=1初始：13865977649271

kk

1I

i=2一趟：[276597764938]

ttttI

jjjjj

二趟：97764938]

三趟:13

四趟:13

五趟:13

六趟:13

排序结束:13

26

简单选择排序算法5.txt

(1)查找待排序序列中最小的记录，并将它

和该区间第一个记录交换；

(2)重复(1)到第nT次排序后结束

★¥

*

27

简单选择排序算法分析

简单选择排序所需要的总的比较次

数为当初始文件是有序时，最

0(4)o

小移动记录次数等于0,而当初始文件

是逆序时，每次都要交换记录。

直接选择排序是不稳定的.

■

28

选择排序-----堆排序的引入

堆排序是简单选择排序的改进。用直接

选择排序从n个记录中选出关键字值最小的

记录要做nT次比较，然后从其余nT个记录

中选出最小者要作n-2次比较。显然，相邻

两趟中某些比较是重复的。为了避免重复比

较，可以采用树形选择排序比较。

29

堆排序的引入

树形选择排序总的比较次数为0(nlog2n),

与直接选择排序比较，减少了比较次数，

但需要增加额外的存储空间存放中间比较

结果和排序结果。

31

堆的定义

n个元素的序列（kl,k2,kn）,当且仅当满足下

列关系时,称之为堆

'ki<k2i'ki>k2i

或(i=l,2,……Ln/2j)

.ki<k2i+l、ki2k2i+l

、例(13,38,27,50,76,65,49,97)

例(96,83,27,38,11,9)l7J

可将堆序列看成完全二叉树，则堆顶

元素（完全二叉树的根）必为序列中

n个元素的最小值或最大值32

堆排序的基本思路

堆排序的基本思路：对一组待排序的记

录序列，先将其关键字按堆的定义排列一个

序列（称初建堆），找到了最小（最大）关

键字，将其取出。用剩余的nT个元素再重建

堆，便可得到次小（次大）值。如此反复执

行，直到全部关键字排好序为止。

■

33

7697

纱u—

5049382750493827

1313

输出：132738495065输出：13273849506576

97.

76,65

50493827

13

输出：1327384950657697★4

36

堆排序的关键问题

堆排序需解决的两个问题：

♦如何由一个无序序列建成一个堆？

♦如何在输出堆顶元素之后，调整剩

余元素，使之成为一个新的堆？

37

堆排序的关键问题

第二个问题解决方法—筛选算法8.6.txt

方法：输出堆顶元素之后，以堆中最后一个元素替

代之；然后将根结点值与左、右子树的根结点值进

行比较，并与其中小者进行交换；重复上述操作，

直至叶子结点，将得到新的堆，称这个从堆顶至叶

子的调整过程为“筛选”。

・第一个问题解决方法—建堆

方法：从无序序列的第Ln/2」个元素（即此无序序列

对应的完全二叉树的最后一个非终端结点）起,」至/

第一个元素止，进行反复筛选。★¥

38

堆排序的算法及分析算法8.7.txt

堆排序只需要一个记录大小的辅助空间o

堆排序算法的时间复杂度为0(nlogn)o

堆排序是一种不稳定的排序方法。

■

40

归并我E序

归并排序：把两个或多个有序表进行合

并，得到一个新的有序表。将两个有序子文

件合并成一个有序文件，称为二路归并。

*

41

2一路归并排序过程

♦设初始序列含有n个记录，则可看成n个有

序的子序列，每个子序列长度为1

两两合并，得到［n/2」个长度为2或1的有序

子序列

再两两合并,如此重复，直至

得到一个长度为n的有序序列为止

■

42

2一路归并排序过程

例初始关键字:

一趟归并后:

二趟归并后：

三趟归并后:

43

2-路归并排序的关键问题

合并是归并排序的核心，即将两个首

尾相连的有序子表合并成一个有序子

表。在合并的基础上进行一趟排序，

在一趟排序的基础上完成多趟排序。

★

44

合并的算法算法8.8.txt.

1）设数组r中第一个有序子表从第h个记录开始至第m个

记录为止。即r[h]到r[m],第二个有序子表从第m+1

个记录开始到第w个记皋为止，即r[m+l]到r[w],最

后形成的有序表为r[h]到r[w]；

2）设置I,j,k分别指向（1）中所指的三个有序表的第一

个单元。

3）比较巾]和山]的关键字值的大小，若巾].keySr|j].key,

则将第一个有序子表的记录r国复制到数组a[k]中，并

使i++,k++;

4）否则，将第二个有序子表的记录内]复制到a[k]中]并

使j++,k++。依次类推，直到全部记录复制到r[h]却*

r[w]中。»

45

一趟归并的算法算法8.9.txt.

把数组r中的长度为s的相邻有序子表两

两合并，归并成一个长度为2s的有序子

表，存于t数组中。

46

多趟合并的算法制去8.10.txt

思路是：第一趟有序子表长S为1,以后

每趟s加倍。第一趟将r数组进行归并后

存于t数组；第二趟将t数组归并后存于

r数组；依次类推，若归并的趟数为奇

数，需从t数组复制到r数组。

★

47

归并排序算法分析

归并排序的总的时间复杂度为0(nlog2n)。

归并排序需要的附加存储空间为0(n),所需

辅助空间较大。

二路归并排序是稳定的。

★¥

48

*基数排序

基数排序是和前面所述的各种排序方法完

全不同的一种排序方法。前面介绍的几种排序

方法，都是根据关键字之间的比较和移动记录

来实现的，基数排序不需要进行记录关键字问

的比较，而是根据组成关键字的各位值，即借

助于多关键字排序的思想，用“分酉己”和“收

集”的方法进行排序。

■

49

多关键字的排序

•假设有n个记录的序列

•{RI,R2,Rn）

每个记录Ri中含有d个关键字（Ki°,

Ki1,…，。廿1）,则称上述记录序列对关键

字（Ki°,Ki1,…，KidT）有序是指：对于序

列中任意两个记录Ri和Rj（l<i<j<n）都满

足下列（词典）有序关系：

•（Ki°,Ki<…，Ki="（叼0,Kj<…，叼匕

其中K°被称为“最主”位关键字，KdT被称牛

为“最次”位关键字。★

50

实现多关键字排序通常有两种作法:

最高位优先MSD法：失对K0进行排序，并按K0的

不同值将记录序列分成若干子序列之后，分别

对K1进行排序，…，依次类推，直至最后对最

次位关键字排序完成为止。

最低位优先LSD法：先对KdT进行排序，然后对

Kd-2进行排序，依次类推，直至对最主位关键

字K0排序完成为止。排序过程中不需要根据

“前一个，，关键字的排序结果，将记录序列分

割成若干个（“前一个”关键字不同的）子序列。

★★

■

51

例如：学生记录含三个关键字：系别、班号和班

内的序列号，其中以系别为最主位关键字。

LSD的排序过程如下：

无序序列1,2,152,3,182,1,20

对K2排序1,2,152,3/82,1,20

对K1排序2,1,201,2/52,3/8

对K0排序1,2,152,1,202,3,18

52

MSD法和LSD法的比较

比较MSD法和LSD法，一般来讲，LSD

法要比MSD法来得简单，因为LSD法是从

头到尾进行若干次分配和收集，执行的

次数取决于构成关键字值的成分为多少；

而MSD法则要处理各序列与子序列的独

立排序问题，就可能复杂一些。

■

53

链式基数排序

假如多关键字的记录序列中，每个关键字的串值

范围相同，则按LSD法进行排序日寸，可以采用

“分配-收集”的方法，其好处是不需要进行关

键字间的比较。

对于数字型或字符型的单关键字，可以看成是由

多个数位或多个字符构成的多关键字，此时可以

采用这种“分配-收集”的办法进行排序，称作

基数排序法。

■

54

鱼

链式基数排序篱去8.11.txt

在计算机上实现基数排序时，应采用链表作存

储结构，即链式基数排序，具体作法为：

待排序记录以指针相链，构成一个链表；

“分配”时，按当前“关键字位”所隼值，

将记录分配到不同的“链队列”中，每个队

列中记录的“关键字位”相同；

“收集”时，按当前关键字位取值从小到大

将各队列首尾相链成一个链表；

对每个关键字位均重复2）和3）两步。

■

55

链式基数排序

•例如：

p―369-367―167―239―237―138-230-139

•第一次分配得到

•f[0]—230-r[0]

•f⑺―367-167—237—r[7]

•f网一138-r[8]

•f[9]-369-239—139—r[9]

•第一次收集得到

p一230—367―167-237-138―368―239—139

■

56

•第二次分配得到

f[3]—230-237—138—239—139—r[3]

•f[6]-36，T167T368—r[6]一

•第二次收集得到

p一230T237Tl38-239—139T367Tl67-368

•第三次分配得到

•f[l]—138—139Tl67—r[l]

•f[2]->230—237—239—r[2]

•f[3]—367-368—r[3]

•第三次收集之后便得到记录的有序序列

p-138—139Tl67-230—237T239—36726升

57

链式基数排序分析

链式基数的E序算法对数据进行d趟扫描，每趟需

时间O(n+j)。因此总的计算时间为O(d(n+j))。对

于不同的基数j所用的时间是不同的。当n较大或d

较小时，这种方法较为节省时间。

基数排序适用于链式存储结构的记录的排序，它要

求的附加存储量是j个队列的头、是指针。所以，

需要0(n+j)辅助空间。

基数排序是一种稳定的排序方法。

★¥

■

58

各种内部排序方法性能比较

方法平均时间最坏情况辅助存储

简单排序O(n2)O(n2)0(1)

2

快速排序O(nlog2n)O(n)O(nlog2n)

堆排序O(nlog2n)O(nlog2n)0(1)

归并排序O(nlog2n)O(nlog2n)O(n)

基数排序O(d(n+j))O(d(n+j))O((n+j)

■

59

各种内部排序方法性能比较

1)从平均时间而言：快速排序最佳。但在最坏情况下时间性

能不如堆排序和归并排序。

2)从算法简单性看：由于直接选择排序、直接插入排序和冒

泡排序的算法比较简单，将其认为是简单算法，都包含在

上图中的“简单排序”中。对于希尔排序、堆排序、快速

排序和归并排序算法，其算法比较复杂，认为是复杂排序。

3)从稳定性看：直接插入排序、冒泡排序和归并排序是稳定

的；而希尔排序、直接选择排序、快速排序和堆排序是不

稳定排序。

4)从待排序的记录数n的大小看，n较小时，宜采用简单排序；

而n较大时宜采用改进排序。★A

■

60

___________选择排序的方法____________

(1)当待排序记录数n较大时，若要求排序稳定，

则采用归并排序。

(2)当待排序记录数n较大，关键字分布随机，而

且不要求稳定时，可采用快速排序；

(3)当待排序记录数n较大，关键字会出现正、逆

序情形，可采用堆排序(或归并排序)。

(4)当待排序记录数n较小，记录已接近有序或随

机分布时，又要求排序稳定，可采用直接插入排序。

(5)当待排序记录数n较小，且对稳定性不作筮热

时，可采用直接选择排序。■

61

*夕卜部排序简介

在实际问题中，经常会遇到输入文件中记录的

数量很大，计算机的内存不能容纳时，排序过

程必须借助外部存储器才能完成，这时的排序

就称为外部排序。

★★

62

外存信息的存取磁带

磁带是涂上一层磁性材料的窄带，磁带

卷在带盘上，带盘安装在磁带驱动器的

转轴上。驱动器控制磁带盘转动，带动

磁带移动，通过读/写磁头进行读/写信

息的操作。

63

外有信息的存取磁盘

磁盘存隼信息时，首先要确定信息所在的柱面，

再将磁头移动到所需磁道