北京邮电大学自动化学院：《数据结构》第九章 排序

第9章排序 91概述 1、排序 ●排序是计算机程序设计中的一种重要操作,它的功能是将一个 数据元素(或记录)的任意序列,重新排列成一个按关键字有 序序列。 ●假设含n个记录的序列为:·其相应的关键字序列为 ●{R1,R2,……,Rn}(9.1) {K1,K 2 njs 需确定1,2,…,n的一种排列P1,P2,…,Pn,使其相 应的关键字满足如下的非递减(或非递增)关系 Kp1≤Kp2≤…Kpn,即使(91)式的序列成为一个按关键字 有序的序列{Rp1,Rp2,……,Rpn},这样一种操作称为排序。 北京邮电大学自动化学院

北京邮电大学自动化学院 1 第9章 排序 ⚫ 9.1 概述 ⚫ 1、排序 ⚫ 排序是计算机程序设计中的一种重要操作，它的功能是将一个 数据元素（或记录）的任意序列，重新排列成一个按关键字有 序序列。 ⚫ 其相应的关键字序列为 ⚫ {K1，K2，……，K n }， ⚫ 假设含n个记录的序列为： ⚫ {R1，R2，……，R n } (9.1） ⚫ 需确定1，2，……， n的一种排列P1，P2，……，P n，使其相 应的关键字满足如下的非递减（或非递增）关系 KP1KP2……KP n，即使（9.1）式的序列成为一个按关键字 有序的序列{RP1，RP2，……，RPn}，这样一种操作称为排序

●2、稳定的、非稳定的 假设K产K(1m,1jn,词)且在排序前的序列中 R领先R(即j)。 ●若在排序后的序列中R仍领先R,则称所用的排序方法是稳 定的; ●反之,若可能使排序后的序列中R领先于R,则称所用的 排序方法是不稳定的。 3、内部排序、外部排序 ●内部排序:指的是待排序记录存放在计算机随机存储器中 进行的排序过程。 外部排序:指的是排序记录的数量很大,以致内存一次 不能容纳全部记录,在排序过程中尚需对外存进行访问 的排序过程。 北京邮电大学自动化学院

北京邮电大学自动化学院 2 ⚫ 2、稳定的、非稳定的 ⚫ 3、内部排序、外部排序 ⚫ 假设Ki=Kj（1  i  n，1  j  n，ij）且在排序前的序列中 Ri领先Rj（即i<j）。 ⚫ 内部排序：指的是待排序记录存放在计算机随机存储器中 进行的排序过程。 ⚫ 外部排序：指的是排序记录的数量很大，以致内存一次 不能容纳全部记录，在排序过程中尚需对外存进行访问 的排序过程。 ⚫ 反之，若可能使排序后的序列中Rj领先于Ri，则称所用的 排序方法是不稳定的。 ⚫ 若在排序后的序列中Ri仍领先Rj，则称所用的排序方法是稳 定的；

°4、排序方法 入排序:直接插入排序、折半插入排序、希尔排序 交换排序:冒泡排序、快速排序 选择排序:简单选择排序、树形选择排序、堆排序 归并排序:2-路归并排序 ●基数排序:多关键字排序、链式基数排序 ●如果按内部排序过程中所需的工作量来区分,可分为: (1)简单排序,其时间复杂度为Tn)=O(n2) (2)先进的排序方法,其时间复杂度为Tn)= o(nlogn (3)基数排序,其时间复杂度为T(m)=O(dn) 5、排序基本操作: (1)比较两个关键字大小; (2)将记录从一个位置移动到另一个位置。 北京邮电大学自动化学院

北京邮电大学自动化学院 3 ⚫ 4、排序方法 ⚫ 插入排序：直接插入排序、折半插入排序、希尔排序 ⚫ 交换排序：冒泡排序、快速排序 ⚫ 选择排序：简单选择排序、树形选择排序、堆排序 ⚫ 归并排序：2-路归并排序 ⚫ 基数排序: 多关键字排序、链式基数排序 ⚫ 如果按内部排序过程中所需的工作量来区分，可分为： ⚫ （1）简单排序，其时间复杂度为T(n)=O(n²) ⚫ （2）先进的排序方法，其时间复杂度为T(n)=O(nlogn) ⚫ （3）基数排序，其时间复杂度为T(n)=O(d.n) ⚫ 5、排序基本操作 ： ⚫ （1）比较两个关键字大小； ⚫ （2）将记录从一个位置移动到另一个位置

91插入排序 ●插入排序的基本思想是:每一步将一个待排序的记录,按 其主关键字的大小插入到前面已经排序的文件中适当位置 上,直至全部插完为止。 ●1、直接插入排序 直接插入排序是一种最简单的排序方法,它的基本操作 是将一个记录插入到已排好的有序表中,从而得到一个 新的、记录数增加1的有序表。 例如:已知待排序的一组记录的初始排列如下所示:R (49),R(38),R(65),R(97),R(76),R (13),R(27),R(19)。 北京邮电大学自动化学院 4

北京邮电大学自动化学院 4 ⚫ 插入排序的基本思想是：每一步将一个待排序的记录，按 其主关键字的大小插入到前面已经排序的文件中适当位置 上，直至全部插完为止。 9.1 插入排序 ⚫ 1、直接插入排序 ⚫ 直接插入排序是一种最简单的排序方法，它的基本操作 是将一个记录插入到已排好的有序表中，从而得到一个 新的、记录数增加1的有序表。 ⚫ 例如：已知待排序的一组记录的初始排列如下所示：R （49），R（38），R（65），R（97），R（76），R （13），R（27），R（19）

1、直接插入排序 很设在排序过程中,前四个记录已按关键字递增的次序,重 新排列,构成一个含4个记录的有序序列: ●{38,49,65,97} (93) ●现要将第5个(关键字为76)的记录插入上述序列,可以得 到一个新的含5个记录的有序序列,则首先要找到插入的位 置,然后进行插入。 ●假设从R(97)起向左进行顺序查找,由于65≤76≤97,则 R(76)应插入在R(65)和R(97)之间,从而得到下列新 的有序序列: {R(38),R(49),R(65),R(76),R(97)}(9.4) ●称从式(93)到式(94)的过程为一趟直接插入排序。 北京邮电大学自动化学院

北京邮电大学自动化学院 5 1、直接插入排序 ⚫ 假设在排序过程中，前四个记录已按关键字递增的次序，重 新排列，构成一个含4个记录的有序序列: ⚫ 现要将第5个（关键字为76）的记录插入上述序列，可以得 到一个新的含5个记录的有序序列，则首先要找到插入的位 置，然后进行插入。 ⚫ 假设从R（97）起向左进行顺序查找，由于65 76  97，则 R（76）应插入在R（65）和R（97）之间，从而得到下列新 的有序序列: ⚫ {R（38），R（49），R（65），R（76），R（97）} (9.4) ⚫ 称从式（9.3）到式（9.4）的过程为一趟直接插入排序。 ⚫ {38，49，65，97} (9.3)

1、直接插入排序 般情况下,第j趟直接插入排序的操作为: 在含有i-1个记录的有序子序列r1.-1中插入一个记录r[ 后,变成含有个记录的有序子序序列r1. ●并且,和顺序查找类似,为了在查找插入位置的过程中避 免数组下标出界,在r[0处设置监视哨。 在自-1起往前搜索的过程中,可以同时后移记录。 整个排序过程为进行n-1趟插入,即:先将序列中的第一个记 录看成是一个有序序列的子序,然后从第2个记录起逐个进行 插入直至整个序列变成按关键字非递减有序序列为止。 北京邮电大学自动化学院

北京邮电大学自动化学院 6 ⚫ 一般情况下，第i趟直接插入排序的操作为： ⚫ 在含有i-1个记录的有序子序列r[1…i-1]中插入一个记录r[i] 后，变成含有i个记录的有序子序序列r[1…i]； ⚫ 并且，和顺序查找类似，为了在查找插入位置的过程中避 免数组下标出界，在r[0]处设置监视哨。 ⚫ 整个排序过程为进行n-1趟插入，即：先将序列中的第一个记 录看成是一个有序序列的子序，然后从第2个记录起逐个进行 插入直至整个序列变成按关键字非递减有序序列为止。 ⚫ 在自i-1起往前搜索的过程中，可以同时后移记录。 1、直接插入排序

1、直接插入排序 例 (49386597761327 Chi Txt i=238(3849)6597761327 i365(384965)97761327 i=497(38496597)761327 i=576(3849657697)1327 613(133849657697)27 i727(13273849657697 排序结果:(3273849657697) 北京邮电大学自动化学院

北京邮电大学自动化学院 7 例 49 38 65 97 76 13 27 i=2 38 (38 49) 65 97 76 13 27 i=3 65 (38 49 65) 97 76 13 27 i=4 97 (38 49 65 97) 76 13 27 i=5 76 (38 49 65 76 97) 13 27 i=6 13 (13 38 49 65 76 97) 27 i=1 ( ) i=7 (13 38 49 65 76 97) 27 27 j j j j j j 27 38 49 65 76 97 排序结果：(13 27 38 49 65 76 97) 1、直接插入排序

1、直接插入排序 Ch8 txt 当待排序列中记录按关键字非递减有序排列(正序)所需进行 关键字间比较的次数达最小值义1=n-1 记录不需要移动 当待排序列中记录按关键字非递增有序排列(逆序)所需 进行关键字间比较的次数达最大值∑=(+2n= 记录移动的次数也达到最大值之(+1)=(n+X 2 我们可取上述最小值和最大值的平均值,作为直接插入排序时 所需进行关键字间的比较次数和移动记录的次数,约为n24 由此,直接插入排序的时间复杂度为o(n2)。 ch8 1.c 北京邮电大学自动化学院

北京邮电大学自动化学院 8 Ch8_1.c ⚫ 当待排序列中记录按关键字非递减有序排列(正序）所需进行 关键字间比较的次数达最小值 1 1 2  = − = n n i 2 ( 4)( 1) ( 1) 2 + −  + = = n n i n i 2 ( 2)( 1) 2 + −  = = n n i n i ⚫ 记录移动的次数也达到最大值 ⚫ 当待排序列中记录按关键字非递增有序排列（逆序）所需 进行关键字间比较的次数达最大值 ⚫ 我们可取上述最小值和最大值的平均值，作为直接插入排序时 所需进行关键字间的比较次数和移动记录的次数，约为n 2 /4。 由此，直接插入排序的时间复杂度为O（ n 2）。 ⚫ 记录不需要移动。 1、直接插入排序

2、其它插入排序 ●(1)折半插入排序 ●由于插入排序的基本操作是在一个有序表中进行查找和插 入,则从上章的讨论可知,这个“查找”操作可利用“折半 查找”来实现,由此进行的插入排序称之为折半插入排序。 ●直接插入排序的基本操作是向有序表中插入一个记录,平均情况 下总比较次数约为n214。既然是在有序表中确定插入位置,可以 不断二分有序表来确定插入位置,通过待插入记录与有序表居中 的记录按关键码比较,将有序表一分为二,下次比较在其中一个 有序子表中进行,这样继续下去,直到要比较的子表中只有一个 记录时,比较一次便确定了插入位置。 北京邮电大学自动化学院

北京邮电大学自动化学院 9 2、其它插入排序 ⚫ （1）折半插入排序 ⚫ 由于插入排序的基本操作是在一个有序表中进行查找和插 入，则从上章的讨论可知，这个“查找”操作可利用“折半 查找”来实现，由此进行的插入排序称之为折半插入排序。 ⚫ 直接插入排序的基本操作是向有序表中插入一个记录，平均情况 下总比较次数约为n 2 /4。既然是在有序表中确定插入位置，可以 不断二分有序表来确定插入位置，通过待插入记录与有序表居中 的记录按关键码比较，将有序表一分为二，下次比较在其中一个 有序子表中进行，这样继续下去，直到要比较的子表中只有一个 记录时，比较一次便确定了插入位置

●折半插入排序 (30)1370853942 20 i=213(1330)70853942620 6(6133039427085)20 i=820 133039427085)20 m i-820(9133039427085)20 i=820(613.3039427085)20 F=820(6 3039427085)20 i=820613203039427085 北京邮电大学自动化学院 10

北京邮电大学自动化学院 10 i=1 (30) 13 70 85 39 42 6 20 i=2 13 (13 30) 70 85 39 42 6 20 i=7 6 (6 13 30 39 42 70 85 ) 20 …. i=8 20 (6 13 20 30 39 42 70 85 ) ⚫折半插入排序 i=8 20 (6 13 30 39 42 70 85 ) 20 s m j i=8 20 (6 13 30 39 42 70 85 ) 20 s m j i=8 20 (6 13 30 39 42 70 85 ) 20 s m j i=8 20 (6 13 30 39 42 70 85 ) 20 j s