数据结构 第十章

1、第十章 内部排序,10.2 插入排序,10.1 概述,10.3 快速排序,10.4 选择排序,10.5 归并排序,10.6 基数排序,10.7 各种内部排序方法的比较讨论,10.1 概述,排序(sorting),* 排序操作的对象记录的序列，通常称作文件。,排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。,例如：将下列关键字序列,52, 49, 80, 36, 14, 58, 61, 23, 97, 75,调整为,14, 23, 36, 49, 52, 58, 61 ,75, 80, 97,设含n 个记录的序列为( r1, r2, ， rn )， 其

2、相应的关键字序列为 ( k1, k2, ，kn )，,这些关键字相互之间可以进行比较，即在 它们之间存在着非递减关系 kp1kp2kpn,按此关系将相应记录序列重新排列为 ( rp1, rp2, ，rpn ) 的操作称作排序。,排序的形式化定义,内部排序和外部排序,若待排序记录可全部放入内存，整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；,若待排序记录的数量很大，以至内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问，则称此类排序问题为外部排序。,排序方法的稳定性,对于一种排序方法，若排序后具有相同关键字的记录仍维持原来的相对次序，则称之为稳定的，否则称之为不稳定的。,

3、例：,按成绩非递增排序,排序方法的稳定性是由方法本身决定的。对不稳定的排序方法而言，不管其描述形式如何，总能举出一个说明不稳定的实例来；反之，对稳定的排序方法，总能找到一种不引起不稳定的描述形式。,例：举重比赛中的运动员成绩表,排序前按体重递增有序，排序后按成绩非递增有序。, 需采用稳定的排序方法,内部排序的方法,内部排序的过程是一个逐步扩大记录的有序序列长度的过程。,经过一趟排序,有序序列区,无 序 序 列 区,有序序列区,无 序 序 列 区,基于不同的“扩大”有序序列长度的方法，内部排序方法大致可分下列几种类型：,插入类,交换类,选择类,归并类,其它方法,1. 插入类,将无序子序列中的一个

4、或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。,2. 交换类,通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。,3. 选择类,从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。,4. 归并类,通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。,5. 其它方法,存储方式,排序操作通常可以在下列一些存储结构上进行：,顺序表,链表（线性链表、静态链表）,索引顺序表,讨论约定,#define maxsize 20 / 顺序

5、表最大长度的假定值 typedef int keytype; / 不妨设关键字类型为整型 typedef struct keytype key; / 关键字域 infotype otherinfo; / 其他域 rcdtype; / 记录类型 typedef struct rcdtype rmaxsize+1; / r0闲置或用作监视哨单元 int length; / 顺序表长度 sqlist; / 顺序表类型,待排序记录的数据类型,10.2 插入排序,有序序列r1.i-1,ri,无序序列 ri.n,一趟插入排序的基本思想：,有序序列r1.i,无序序列 ri+1.n,实现“一趟插入排序”可分三

6、步进行：,3将ri 插入(复制)到rj+1的位置上。,2将rj+1.i-1中的所有记录均后移 一个位置；,1在r1.i-1中查找ri的插入位置， r1.j.key ri.key rj+1.i-1.key；,直接插入排序（基于顺序查找）,不同的具体实现方法导致不同的算法描述,折半插入排序（基于折半查找）,希尔排序（基于逐趟缩小增量）,if (lt(l.ri.key, l.ri-1.key) l.r0 = l.ri; l.ri = l.ri-1; for( j=i-2; lt(l.r0.key, l.rj.key); -j ) l.rj+1 = l.rj; l.rj+1 = l.r0; ,在有序序

7、列 r1.i-1 中查找 ri 的插入位置时，直接利用 “顺序查找”来实现。,10.2.1 直接插入排序,void insertsort( sqlist / insertsort,算法10.1 (p265),实例： 初始关键字 （49） 38 65 97 76 13 27 49,i=2 （38）（38 49） 65 97 76 13 27 49,i=3 （38）（38 49 65）97 76 13 27 49,i=4 （38）（38 49 65 97）76 13 27 49,i=5 （76）（38 49 65 76 97）13 27 49,i=6 （13）（13 38 49 65 76 97）

8、27 49,i=7 （27）（13 27 38 49 65 76 97）49,i=8 （49）（13 27 38 49 49 65 76 97）,监视哨l.r0,内部排序的时间分析：,实现内部排序的基本操作有两个：,（2）“移动”记录。,（1）“比较”序列中两个关键字的 大小；,直接插入排序性能分析,最好的情况（文件初始状态顺序有序）：,最大比较次数：,最坏的情况（文件初始状态逆序有序）：,最小移动次数：,最小比较次数：,最大移动次数：,因为 r1.i-1 是一个按关键字有序的有序序列，则可以利用折半查找实现“在r1.i-1中查找ri的插入位置”，如此实现的插入排序为折半插入排序。,10.2.

9、2 折半插入排序,void binsertsort( sqlist / for / binsertsort,或 high +1,算法10.2 (p267),14 36 49 52 80,58 61 23 97 75,i,low,high,m,m,low,low,m,high,14 36 49 52 58 61 80,23 97 75,i,low,high,m,high,m,high,m,low,例如:,再如:,插入 位置,插入 位置,l.r,l.r,无论哪种情况low=high+1始终为插入位置。,10.2.3 希尔排序(缩小增量排序),基本思想：对待排记录序列先作“宏观”调整，再作“微观”调

10、整。,即先对记录进行“跳跃式”的移动，再进行“一步步挪动”。 具体做法为：,将记录序列分成若干子序列，分别对每个子序列进行插入排序。,其中，d 称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为 1。,例如：将 n 个记录分成 d 个子序列： r1，r1+d，r1+2d，r1+kd r2，r2+d，r2+2d，r2+kd rd，r2d，r3d，rkd，r(k+1)d ,例：(增量序列：5，3，1) 初始关键字： 49 38 65 97 76 13 27 49 55 04,49 13,一趟排序结果：13 27 49 55 04 49 38 65 97 76,38 27,65 49

11、,97 55,76 04,13 55 38 76,27 04 65,49 49 97,二趟排序结果：13 04 49 38 27 49 55 65 97 76,三趟排序结果：04 13 27 38 49 49 55 65 76 97,选定一个增量序列 nd1d2dt=1， 其中 n 文件长度； di (1it) 增量(正整数)； t 增量个数、排序趟数。 将文件按 d1 分组，彼此相距 d1 的记录划为一组，在各组内采用直接插入法进行排序。 分别按 d2, dt 重复上述分组和排序工作。,void shellinsert( sqlist / if / shellinsert,算法10.4 (p

12、272),void shellsort( sqlist / binsertsort,存在不同的希尔排序算法： 算法中可采用监视哨技术 算法中可包含增量序列的计算及保存 组内排序可采用其他方法，如起泡排序,算法10.5 (p272),关于增量序列,希尔排序的增量序列可以有各种取法，任何正整数的递减序列d1, d2, dt，只要 d1n，dt=1，增量序列中的值没有除1之外的公因子，原则上都可以作为希尔排序的增量序列。,希尔排序算法的时间复杂度不仅是 n 的函数，还是所取增量序列的函数。,10.3 快速排序,c.a.r.hoare (霍尔) 1962.,一、起泡排序,二、一趟快速排序,三、快速排序

13、,四、快速排序的时间分析,一、起泡排序,假设在排序过程中，记录序列r1.n的状态为：,第 i 趟起泡排序,无序序列r1.n-i+1,有序序列 rn-i+2.n,n-i+1,无序序列r1.n-i,有序序列 rn-i+1.n,比较相邻记录，将关键字最大的记录交换到 n-i+1 的位置上,void bubblesort(elem r , int n) while (i 1) / while / bubblesort,i = n;,i = lastexchangeindex; / 本趟进行过交换的 / 最后一个记录的位置,if (rj+1.key rj.key) swap(rj, rj+1); las

14、texchangeindex = j; /记下进行交换的记录位置 /if,for (j = 1; j i; j+),lastexchangeindex = 1;,时间分析:,最好的情况（关键字在记录序列中顺序有序）： 只需进行一趟起泡,“比较”的次数：,最坏的情况（关键字在记录序列中逆序有序）： 需进行n-1趟起泡,“比较”的次数：,0,“移动”的次数：,“移动”的次数：,n-1,二、一趟快速排序（一次划分）,目标：找一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。,致使一趟排序之后，记录的无序序列rs.t将分割成

15、两部分：rs.i-1和ri+1.t，且 rj.key ri.key rj.key (sji-1) 枢轴 (i+1jt)。,s,t,low,high,设 rs=52 为枢轴,将 rhigh.key 和 枢轴的关键字进行比较，要求rhigh.key 枢轴的关键字,将 rlow.key 和 枢轴的关键字进行比较，要求rlow.key 枢轴的关键字,high,23,low,high,low,例如,low,high,high,high,low,52,52,52,80,14,可见，经过“一次划分” ，将关键字序列 52, 49, 80, 36, 14, 58, 61, 97, 23, 75 调整为: 23

16、, 49, 14, 36, (52) 58, 61, 97, 80, 75,在调整过程中，设立了两个指针： low 和high，它们的初值分别为： s 和 t，,之后逐渐减小 high，增加 low，并保证 rhigh.key52，和 rlow.key52,否则进行记录的“交换”。,例：,基于交换的划分策略,基于交换的一趟快速排序算法 (p274),int partition( sqlist / patition,算法10.6(a),s,t,low,high,设 rs=52 为枢轴,high,23,low,80,high,14,low,52,例如,r0,52,low,high,high,hig

17、h,low,例：,算法10.6(b),一趟快速排序算法 (p274),int partition( sqlist / patition,算法10.6(c),改进的一趟快速排序算法,int partition( sqlist / patition,三、快速排序,首先对无序的记录序列进行“一次划分”，之后分别对分割所得两个子序列“递归”进行快速排序。,无 序 的 记 录 序 列,无序记录子序列(1),无序子序列(2),枢轴,一次划分,分别进行快速排序,void qsort( sqlist / qsort,快速排序算法 (p275276算法10.7, 10.8),void quicksort( sq

18、list / quicksort,第一次调用函数 qsort 时，待排序记录序列的上、下界分别为 1 和 l.length。,快速排序实例 (p275),快速排序所采用的策略 分治法,此时，总的比较次数为,快速排序性能分析,快速排序的平均时间复杂度为o(nlog2n)，但在最坏情况下，即待排记录的初始状态为按关键字有序，快速排序将蜕化为起泡排序，其时间复杂度是o(n2)。,快速排序的所谓“快速”，是对当n 较大时的平均时间性能而言，并不是任何情况下都快，当n 很小或待排序文件基本有序时，不如用直接插入排序或起泡排序。,快速排序需要一个栈空间来实现递归，因此辅助空间多于直接插入排序和起泡排序。,

19、为改善快速排序在最坏情况下的时间性能，在选取枢轴记录时，可采用“三者取中”预处理技术。,即：在进行一次划分之前，先对 l.rlow.key, l.rhigh.key 和 l.r(low+high)/2.key 进行相互比较，然后取关键字为“三者之中”的记录为枢轴，将其与 l.rlow 互换，算法10.6 其余部分不变。,快速排序算法的改进措施,10.4 选择排序,简 单 选 择 排 序,堆 排 序,10.4.1 简单选择排序,假设排序过程中，待排记录序列的状态为：,有序序列r1.i-1,无序序列 ri.n,第 i 趟 简单选择排序,从中选出 关键字最小的记录,有序序列r1.i,无序序列 ri+

20、1.n,void selectsort( sqlist / selectsort,简单选择排序算法,简单选择排序所需进行的关键字比较次数与文件初始状态无关。,最小移动次数： 0 最大移动次数： 3(n-1),简单选择排序时间性能分析,简单选择排序所需进行的记录的移动次数与文件初始状态有关。,比较次数总计：,特点：比较次数多而移动次数少。,填空练习题 1. 对线性表(50, 12, 53, 06, 90, 17, 84, 27, 65, 42) 进行快速排序，所需趟数为 。 3 4 5 6 2. 用简单选择排序法分别对下列线性表进行排 序，线性表 所需的记录移动次数最多。 (1,2,3,4) (

21、4,3,2,1) (2,4,1,3) (3,4,1,2),堆是 n 个元素的序列 ( k1, k2, ,kn )，该序列满足如下条件：,或,定义:,(12, 36, 27, 65, 40, 34, 98, 81, 73, 55),例:,是小顶堆,(12, 36, 27, 65, 40, 14, 98, 81, 73, 55),不是堆,(小顶堆),(大顶堆),10.4.3 堆排序,( i=1, 2,n/2 ),（堆的线性表定义）,若将上述线性表视作一棵完全二叉树的层次序列，则 k2i 是 ki 的左孩子; k2i+1 是 ki 的右孩子。, 堆的完全二叉树定义,一棵完全二叉树，若它的任一分支结点

22、的关键字均不大于（或不小于）其孩子结点的关键字，则称为堆。,12,36,27,65,49,81,73,55,40,34,98,例如:,是堆,14,不,若序列 ( k1, k2, ,kn ) 是小顶堆，则堆顶元素 k1 必为其最小元素。,(10, 15, 56, 25, 30, 70),(70, 56, 30, 25,15,10),(小顶堆),(大顶堆),例：,堆排序即是利用堆的特性对记录序列进行排序的一种排序方法。,例如：,建大顶堆, 98, 81, 49, 73, 36, 27, 40, 55, 64, 12 , 12, 81, 49, 73, 36, 27, 40, 55, 64, 98

23、,交换 98 和 12,重新调整为大顶堆, 81, 73, 49, 64, 36, 27, 40, 55, 12, 98 , 40, 55, 49, 73, 12, 27, 98, 81, 64, 36 ,经过筛选,所谓“筛选”指的是，对一棵左/右子树均为堆的完全二叉树，“调整”根结点使整个二叉树也成为一个堆。,堆,堆,筛选,98,81,49,73,55,64,12,36,27,40,例如:,是大顶堆,12,但在98和12进行互换之后，它就不是堆了，,因此，需要对它进行“筛选”。,98,12,81,73,64,12,98,比较,比较,void heapadjust( heaptype / he

24、apadjust,筛选算法 (p282 算法10.10),heapadjust(h, s, m) 筛选算法。已知 h.rs.m中记录除 h.rs 之外均满足堆的定义，该算法调整h.rs，使 h.rs.m中各记录均满足堆的定义。s 被筛选记录的序号； m 筛选范围的上界；,建堆是一个从下往上进行“筛选”的过程。,40,55,49,73,81,64,36,12,27,98,例如: 排序之前的关键字序列为,12,36,81,73,49,98,81,73,55,现在，左/右子树都已经调整为堆，最后只要调整根结点，使整个二叉树是个“堆”即可。,98,49,40,64,36,12,27,void heap

25、sort( heaptype / 重新调整为大顶堆 / heapsort,堆排序算法 (p282 算法10.11),堆排序的时间复杂度分析：,每向下筛一层，进行 2 次比较，所以对深度为 k 的 堆，一趟筛选所需进行的关键字的比较次数至多为 2(k-1) = 2 log2 n ( k= log2n +1),对 n 个关键字，建成深度为h(=log2n+1)的堆，所需进行的关键字比较的次数至多 4n；(p282),堆排序的时间复杂度为o(nlog2n),调整“堆顶” n-1 次，需进行的关键字的比较次数不超过 2 ( log2(n-1)+ log2(n-2)+log22 ) 2n log2n,堆

26、排序的空间复杂度为o(1),10.5 归并排序,归并排序的基本思想,假设初始序列含有 n 个记录，则可看成是 n 个有序的子序列，每个子序列的长度为1，然后两两归并，得到 n/2 个长度为 2 或 1 的有序子序列；再两两归并，如此重复，直至得到一个长度为 n 的有序序列为止，这种排序方法称为2-路归并排序。,2-路归并排序示例,25 57 48 37 12 92 86,25 57 37 48 12 92 86,25 37 48 57 12 86 92,12 25 37 48 57 86 92,初始关键字,一趟归并之后,二趟归并之后,三趟归并之后,所需趟数 log2n,2-路归并排序的核心操作

27、：将两个位置相邻的记录有序子序列,归并为一个记录的有序序列。,有 序 序 列 rl.n,有序子序列 rl.m,有序子序列 rm+1.n,这个操作对顺序表而言，是轻而易举的。,void merge( rcdtype sr , rcdtype / merge,子序列归并算法,算法10.12 (p283),容易看出，对 n 个记录进行归并排序的时间复杂度为(nlog2n)。即： 每一趟归并的时间复杂度为 o(n)， 总共需进行 log2n 趟。,归并排序性能分析：,归并排序需要和待排记录等数量的辅助空间，即空间复杂度为o(n)。归并排序是需要辅助空间最多的一种排序方法。,递归形式的2-路归并排序算法

28、,如果记录无序序列 rs.t 的两部分 rs.(s+t)/2 和 r(s+t)/2+1.t 分别按关键字有序，则利用上述归并算法很容易将它们归并成整个记录序列是一个有序序列。由此，应该先分别对这两部分进行 2-路归并排序。,例如：,52, 23, 80, 36, 68, 14 (s=1, t=6), 52, 23, 80 36, 68, 14, 52, 2380, 52, 23, 52, 23, 52, 80,36, 6814,3668,36, 68,14, 36, 68, 14, 23, 36, 52, 68, 80 ,23,void msort( rcdtype sr , rcdtype

29、/ msort,递归形式的2-路归并排序算法,算法10.13 (p284),void mergesort( sqlist / mergesort,算法10.14 (p284),10.6 基数排序,基数排序是一种借助“多关键字排序”的思想来实现“单逻辑关键字排序”的内部排序算法。,多关键字的排序,链式基数排序,10.6.1 多关键字的排序,设有n 个记录的序列 ( r1, r2, , rn )，其中每个记录ri 含有d 个关键字( ki1, ki2, kid ) ，,其中: k1 被称为 最主位（最高位）关键字，,kd 被称为 最次位（最低位）关键字。,若对于序列中任意两个记录ri 和rj (1

30、ijn) 都满足下列（词典）有序关系： ( ki1, ki2,kid )( kj1, kj2,kjd ) 则称记录序列 ( r1, r2, ,rn ) 对关键字( k1, k2,kd ) 有序。,实现多关键字排序通常有两种方法: 最高位优先法(msd法) 最低位优先法(lsd法),先对k1进行排序，并按k1 的不同值将记录序列分成若干子序列之后，分别对k2 进行排序，.，依次类推，直至最后对最低位关键字排序完成为止。,最高位优先(most significant digit first)法,例如:学生记录含三个关键字:系别、班号和班内的序列号，其中以系别为最主位关键字。,无序序列,对k1排序,

31、对k2排序,对k3排序,3,2,30,1,2,15,3,1,20,2,3,18,2,1,20,msd的排序过程如下:,1,2,15,2,3,18,2,1,20,3,2,30,3,1,20,1,2,15,2,1,20,2,3,18,3,1,20,3,2,30,1,2,15,2,1,20,2,3,18,3,1,20,3,2,30,先对kd进行排序，然后对kd-1进行排序,，依次类推，直至对最高位关键字 k1 排序完成为止。,最低位优先(least significant digit first)法,排序过程中不需要根据 “前一个” 关键字的排序结果，将记录序列分割成若干个(“前一个”关键字不同的)

32、子序列，对每个关键字都是整个序列参加排序。但对ki(1id)进行排序时，只能用稳定的排序方法。,例如:学生记录含三个关键字:系别、班号和班内的序列号，其中以系别为最主位关键字。,无序序列,对k3排序,对k2排序,对k1排序,3,2,30,1,2,15,3,1,20,2,3,18,2,1,20,1,2,15,2,3,18,3,1,20,2,1,20,3,2,30,3,1,20,2,1,20,1,2,15,3,2,30,2,3,18,1,2,15,2,1,20,2,3,18,3,1,20,3,2,30,lsd的排序过程如下:,msd和lsd只约定按什么样的关键字次序来进行排序，并未规定对每个关键字

33、进行排序时所用的方法。,在按lsd排序时，也可以不利用前几节讨论的各种排序方法，而是通过若干次“分配”和“收集”实现排序，这样做不需要进行关键字的比较。 * 通过“分配-收集”实现排序的方法称作分配排序。,10.6.2 链式基数排序,对于数字型或字符型的单逻辑关键字，可以看成是由多个数位或多个字符构成的多关键字,此时可以按 lsd 法通过“分配-收集”进行排序： 从最低位关键字起，按关键字的不同值依次将序列中记录分配到 rd 个队列中，然后收集之，如此重复 d 次，便可完成排序。 rd 基数（各位关键字的可能取值个数） d 关键字位数,基数排序是一种借助多关键字排序的思想来实现单逻辑关键字排序

34、的内部排序方法。,在计算机上实现基数排序时，为减少所需辅助存储空间，应采用链表作存储结构，即链式基数排序，具体做法为：,待排序记录以指针相链，构成一个链表；,“分配”时，按当前关键字位所取值，将记录分配到相应的链队列中，每个队列中记录的 当前关键字位取值相同；,“收集”时，按当前关键字位取值从小到大依次将各队列首尾相链，成为一个链表;,对每个关键字位均重复 2) 和 3) 两步。,例如：,p369367167239237138230139,进行第一次分配,进行第一次收集,f0 r0,f7 r7,f8 r8,f9 r9,p230,230,367 ,167,237,367167237,138,36

35、8239139,369 ,239,139,138,进行第二次分配,p230237138239139,p230367167237138369239139,f3 r3,f6 r6,230 ,237,138,239,139,367 ,167,369,367167369,进行第二次收集,进行第三次收集之后便得到记录的有序序列,f1 r1,p230237138239139367167369,进行第三次分配,f2 r2,f3 r3,138 ,139,167,230 ,237,239,367 ,369,p138139167,230237239,367369,注意：,“分配”和“收集”的实际操作仅为修改链表中

36、的指针和设置队列的头、尾指针。,基数排序算法的时间复杂度为： o( d( n+rd ) ),其中，分配为o(n)，收集为o(rd)， rd为“基数”，d 为“分配-收集”的趟数。,当n值较大时，基数排序的时间复杂度也可写成：o(dn),10.7 各种内部排序 方法的比较讨论,一、时间性能,1. 平均的时间性能,基数排序,时间复杂度为 o(nlog2n)：,快速排序、堆排序和归并排序,时间复杂度为 o(n2)：,直接插入排序、折半插入排序、 起泡排序、简单选择排序,时间复杂度为 o(n):,2. 当待排记录序列按关键字顺序有序时直接插入排序和起泡排序能达到o(n)的时间复杂度，快速排序的时间性能蜕化为o(n2) 。,3. 简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。,二、空间性能,指的是排序过程中所需的辅助空间大小,1. 所有的简单排序方法(包括：直接插入、折半插入、起泡和简单选择) 和堆排序的空间复杂度为o(1)；,2. 快速排序为o(log2n)，为递归程序执行过程中，栈所需的辅助空间；,3. 归并排序所需辅助空间最多，其空间复杂度为 o(n);,4. 链式基数排序需附设队列首尾指针，则空间复杂度为 o(n+rd)。,三、排序方法的稳定