数据结构课件2第10章排序117

1、10.1 概述概述10.2 插入排序插入排序10.3 快速排序快速排序10.4 选择排序选择排序10.5 归并排序归并排序10.6 基数排序基数排序10.7 各种排序方法的综合比较各种排序方法的综合比较10.1 10.1 概述概述1. 1. 排序的定义排序的定义排序：把排序：把一组一组“无序无序”的记录调整为的记录调整为“有序有序”的记录的记录序列。序列。主要目的就是实现快速查找。主要目的就是实现快速查找。例如例如：将下列关键字序列：将下列关键字序列 52，49，80，36，14，58，61，23，97，75调整为调整为 14，23，36，49，52，58，61，75，80，972 一般情况下

2、，假设含n个记录的序列为 R1, R2, ， Rn 其相应的关键字序列为 K1, K2, ，Kn 这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系 Kp1Kp2Kpn按此固有关系将上式记录序列重新排列为 Rp1, Rp2, ，Rpn 的操作操作称作排序排序。(1) 增排序和减排序：如果排序的结果是按关键字从增排序和减排序：如果排序的结果是按关键字从小到大的次序排列的，就是增排序，否则就是减小到大的次序排列的，就是增排序，否则就是减排序。排序。(2) 稳定排序和不稳定排序：假设稳定排序和不稳定排序：假设Ki=Kj(1i,jn，ij)，且在排序前的序列中且在排序前的序列中Ri领先于领

3、先于Rj(即即ij)。 若在排序后的序列中若在排序后的序列中Ri仍领先于仍领先于Rj，即那些具有即那些具有相同关键字的记录，经过排序后它们的相对次序相同关键字的记录，经过排序后它们的相对次序仍然保持不变，则称这种排序方法是稳定的；仍然保持不变，则称这种排序方法是稳定的； 若若Rj领先于领先于Ri，则称所用的方法是不稳定的。则称所用的方法是不稳定的。 4(3) (3) 内部排序与外部排序：内部排序与外部排序： 在排序中，若数据表中的所有记录的排列过程都是在在排序中，若数据表中的所有记录的排列过程都是在内存中进行的，称为内部排序。内存中进行的，称为内部排序。 由于待排序的记录数量太多，在排序过程中

4、不能同时由于待排序的记录数量太多，在排序过程中不能同时把全部记录放在内存，需要不断地通过在内存和外存把全部记录放在内存，需要不断地通过在内存和外存之间交换数据元素来完成整个排序的过程，称为外部之间交换数据元素来完成整个排序的过程，称为外部排序。排序。53、内部排序方法、内部排序方法 内部排序的过程是一个逐步扩大逐步扩大记录的有序序列长度有序序列长度的过程。经过一趟排序经过一趟排序有序序列区无 序 序 列 区有序序列区无 序 序 列 区逐步扩大记录有序序列长度的方法大致有以下几类：逐步扩大记录有序序列长度的方法大致有以下几类：插入类插入类 交换类交换类 选择类选择类 归并类归并类 其他方法其他方

5、法 插入类插入类 将无序子序列中的将无序子序列中的一个或几个记录一个或几个记录“插入插入”到有序序到有序序列中，从而增加记录的有序序列的长度列中，从而增加记录的有序序列的长度 交换类交换类 通过通过“交换交换”无序序列中的无序序列中的相邻或不相邻的记录相邻或不相邻的记录从从而得到其中而得到其中关键字最小或最大的记录关键字最小或最大的记录，并将它加入到有，并将它加入到有序序列中，以此方法增加记录序序列中，以此方法增加记录的有序序列的长度。的有序序列的长度。7 选择类选择类 从记录的无序子序列中从记录的无序子序列中“选择选择”关键字最小或关键字最小或最大的记录最大的记录，并将它加入到有序序列中，以

6、此方法，并将它加入到有序序列中，以此方法增加记录增加记录的有序序列的长度。的有序序列的长度。 归并类归并类 通过通过“归并归并”两个或两个以上的两个或两个以上的记录有序子记录有序子序列序列，逐步增加记录有序序列的长度。，逐步增加记录有序序列的长度。 其它方法：基数方法其它方法：基数方法8各种排序算法性能的评价：各种排序算法性能的评价：时间时间性能和性能和空间空间性能。性能。 排序算法的时间复杂度可用排序过程中记录之间排序算法的时间复杂度可用排序过程中记录之间关键关键字的比较次数与记录的移动次数字的比较次数与记录的移动次数来衡量。一般情况都按来衡量。一般情况都按平平均时间复杂度均时间复杂度进行估

7、算；对于那些受数据表中记录的初始进行估算；对于那些受数据表中记录的初始排列及记录数目影响较大的算法，按排列及记录数目影响较大的算法，按最好情况和最坏情况最好情况和最坏情况分别进行估算。分别进行估算。9 空间复杂度指算法在执行时所需的附加存储空间复杂度指算法在执行时所需的附加存储空间，也就是用来临时存储数据的内存使用情况。空间，也就是用来临时存储数据的内存使用情况。 若无特别说明，均假定待排序的记录序列采若无特别说明，均假定待排序的记录序列采用顺序表结构来存储，即数组存储方式，并假定用顺序表结构来存储，即数组存储方式，并假定是按关键字递增方式排序。是按关键字递增方式排序。10待排记录的数据类型定

8、义如下待排记录的数据类型定义如下:const MAXSIZE = 1000; / 待排顺序表最大长度待排顺序表最大长度typedef int KeyType; / 关键字类型为整数类型关键字类型为整数类型typedef struct KeyType key; / 关键字项关键字项 InfoType otherinfo; / 其它数据项其它数据项 RcdType; / 记录类型记录类型typedef struct RcdType rMAXSIZE+1; / r0闲置闲置 int length; / 顺序表长度顺序表长度 SqList; / 顺序表类型顺序表类型有序序列R1.i-1Ri无序序列 R

9、i.n一趟直接插入排序的基本思想：有序序列R1.i无序序列 Ri+1.n 在在R1i-1中查找中查找Ri的插入位置，的插入位置， R1j Ri Rj+1i-1 将将Rj+1i-1中的所有记录均后移一个位置；中的所有记录均后移一个位置； 将将Ri 复制到复制到Rj+1的位置上的位置上实现实现“一趟插入排序一趟插入排序”可分三步进行：可分三步进行：13直接插入排序直接插入排序（基于顺序查找）（基于顺序查找）表插入排序表插入排序（基于链表存储）（基于链表存储）不同的具体实现方法导致不同的算法描述不同的具体实现方法导致不同的算法描述折半插入排序折半插入排序（基于折半查找）（基于折半查找）希尔排序希尔排

10、序（基于逐趟缩小增量）（基于逐趟缩小增量）一、直接插入排序一、直接插入排序利用 “顺序查找顺序查找”实现“在R1.i-1中查找查找Ri的插入位置”算法的实现要点：算法的实现要点：从Ri-1起向前进行顺序查找， 监视哨设置在R0；R0 = Ri; / 设置“哨兵”循环结束表明Ri的插入位置为 j +1R0jRifor (j=i-1; R0.keyRj.key; -j); / 从后往前找j=i-1插入位置插入位置 对于在查找过程中找到的那些关键字不小于Ri.key的记录，并在查找的同时实现记录向后移动；for (j=i-1; R0.keyRj.key; -j); Rj+1 = RjR0jRij=

11、i-1上述循环结束后可以直接进行“插入”插入位置插入位置令 i = 2，3，, n, 实现整个序列的排序。for ( i=2; i=n; +i ) if (Ri.keyRi-1.key) 在 R1.i-1中查找Ri的插入位置; 插入Ri ; void InsertionSort(SqList &L) /对记录序列对记录序列R1.n作直接插入排序作直接插入排序 for (i=2;i=L.length; + i) if(LT(L.ri.key, L.r.i-1.key) L.r0=L.ri;/复制为监视哨复制为监视哨 L.ri=L.ri-1; for(j=i-2;LT(L.r0.key,L

12、.rj.key);-j) L.rj+1=L.rj/记录后移记录后移 L.rj+1=L.r0；/插入到正确位置插入到正确位置19【例【例10-1】假设有】假设有7个待排序的记录，它们的关键字分别为个待排序的记录，它们的关键字分别为23，4，15，8，19，24，15，用直接插入法进行排序。，用直接插入法进行排序。【解】直接插入排序过程如下图所示。方括号【解】直接插入排序过程如下图所示。方括号 中为已排中为已排好序的记录的关键字，有两个记录的关键字都为好序的记录的关键字，有两个记录的关键字都为15，为表，为表示区别，将后一个示区别，将后一个15加下划线。加下划线。 初始关键字：23 4 15 8

13、19 24 15第一趟排序结果： 4 23 15 8 19 24 15第二趟排序结果：4 15 23 8 19 24 15第三趟排序结果：第四趟排序结果：第五趟排序结果：第六趟排序结果：4 8 15 23 19 24 15 4 8 15 19 23 24 15 4 8 15 19 23 24 15 4 8 15 15 19 23 2420排序时间分析排序时间分析实现排序的基本操作有两个：实现排序的基本操作有两个：（1）“比较比较”序列中两个关键字的大小；序列中两个关键字的大小；（2）“移动移动”记录记录对于插入排序平均情况下还是对于插入排序平均情况下还是O(n2) 最好的情况最好的情况 最坏的

14、情况最坏的情况 （顺序有序）（顺序有序） （逆序有序）（逆序有序） O(n2) 比较的比较的次数次数 移动的移动的 0次数次数nin211ninni2212ninni2214121 因为因为R R1i-1是一个按关键字有序是一个按关键字有序的有序序列，则可以利用的有序序列，则可以利用折半查找折半查找实现实现“在在R1i-1中查找中查找Ri的插入位置的插入位置”，如此实现的插入排序为折半插入排序。如此实现的插入排序为折半插入排序。22二、折半插入排序二、折半插入排序void BiInsertSort(SqList &L) for(i=2; i=L.length; i+) L.r0=L.r

15、i; /保存待插入元素保存待插入元素 low=1; high=i-1; /设置初始区间设置初始区间 while(low=high+1; -j) L.rj+1=L.rj; /后移元素，空出插入位置后移元素，空出插入位置 L.rhigh+1=L.r0; /将元素插入将元素插入 /for/ BiInsertSort 23ilowhighmmlowlowmhighilowhighmhighmhighmlow例如:再如:插入位置插入位置14 36 49 52 80 58 61 23 97 75L.r14 36 49 52 58 61 80 23 97 75L.r 折半插入排序仅减少了关键字间的比较次数，

16、但记录折半插入排序仅减少了关键字间的比较次数，但记录的移动次数不变。因此折半插入排序的时间复杂度仍为的移动次数不变。因此折半插入排序的时间复杂度仍为O(n2)。折半插入排序的空间复杂度与直接插入排序相同。折半插入排序的空间复杂度与直接插入排序相同。折半插入排序也是一个稳定的排序方法。折半插入排序也是一个稳定的排序方法。 25三、表插入排序三、表插入排序 为了减少在排序过程中进行的“移动”记录的操作，必须改变排序过程中采用的存储结构。利用静态链表进行排序，并在排序完成之后，一次性地调整各个记录相互之间的位置，即将每个记录都调整到它们所应该在的位置上。void LInsertionSort (El

17、em SL ， int n) / 对记录序列SL1.n作表插入排序。 SL0.key = MAXINT ; SL0.next = 1; SL1.next = 0; for ( i=2; i=n; +i ) for ( j=0, k = SL0.next;SLk.key= SLi.key ; j=k, k=SLk.next ) SLj.next = i; SLi.next = k; / 结点i插入在结点j和结点k之间/ LinsertionSort算法中使用了三个指针:其中：p指示第i个记录的当前位置； i指示第i个记录应在的位置； q指示第i+1个记录的当前位置。如何在排序之后调整记录序列？如

18、何在排序之后调整记录序列？void Arrange(Elem SL , int n) p = SL0.next; / p指示第一个记录的当前位置 for(i=1; in; +i) while (pi) p = SLp.next; q = SLp.next; / q指示尚未调整的表尾 if(p!= i) SLpSLi; / 交换记录，使第交换记录，使第i个记录到位个记录到位 SLi.next = p; / 指向被移走的记录指向被移走的记录， /if p = q; / p指示尚未调整的表尾，准备找第i+1个记录 /for / Arrange 四、希尔排序四、希尔排序 基本思想：对待排记录序列先作“

19、宏观”调整，再作“微观”调整。 所谓“宏观”调整，指“跳跃式”的插入排序。 具体做法：（1）首先取一个整数）首先取一个整数d1n，称之为增量，将待排序的记称之为增量，将待排序的记录分成录分成d1个组，凡是距离为个组，凡是距离为d1倍数的记录都放在同一个组，倍数的记录都放在同一个组，在各组内进行直接插入排序，这样的一次分组和排序过在各组内进行直接插入排序，这样的一次分组和排序过程称为一趟希尔排序。程称为一趟希尔排序。（2）再设置另一个新的增量）再设置另一个新的增量d2d1，采用与上述相同的采用与上述相同的方法继续进行分组和排序过程。方法继续进行分组和排序过程。（3）继续取）继续取di+1di，重

20、复步骤重复步骤(2)，直到增量，直到增量d=1，即所即所有记录都放在同一个组中。有记录都放在同一个组中。 31例如：将例如：将n个记录分成个记录分成d个子序列：个子序列：R1，R1+d， R1+2d， R1+kdR2，R2+d， R2+2d， R2+kd Rd，R2d， R3d， Rkd， R(k+1)d 其中，其中，d称为增量，它的值在排序过程中从大到小逐渐称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为缩小，直至最后一趟排序减为1。3225 37 58 63 12 58 46 72 95 84第一趟排序结果：初始关键字：72954684253758631258(a)第二趟

21、排序结果：2537586312467295845825 12 58 46 37 58 63 72 95 84(b)251258463763729584122537465863728495第三趟排序结果：5858(c)希尔排序过程希尔排序过程 33例：例：例如：16 25 12 30 47 11 23 36 9 18 31 第一趟希尔排序，设增量 d =511 23 12 9 18 16 25 36 30 47 31 第二趟希尔排序，设增量 d = 39 18 12 11 23 16 25 31 30 47 36第三趟希尔排序，设增量 d = 1 9 11 12 16 18 23 25 30 3

22、1 36 47 希尔排序的算法如下：希尔排序的算法如下：void ShellInsert(SqList &L, int dk) for(i=dk+1; i0& LT(L.r0.key, L.rj.key);j-=dk) L.rj+dk=L.rj;/记录后移，查找插入位置记录后移，查找插入位置 L.rj+dk=L.r0 ;/插入插入 /if void ShellSort(SqList &L,int dlta,int t) /增量为增量为dlta的希尔排序的希尔排序 for(k=0;kR2.key，就交换就交换R1和和R2在序列中的位置；然后继续比较在序列中的位置；然后继续

23、比较R2.key和和R3.key，并作，并作相同处理；重复此过程，直到相同处理；重复此过程，直到Rn-1.key和和Rn.key比较完成。比较完成。最终最终n个记录中关键字最大的记录被交换到序列的最后个记录中关键字最大的记录被交换到序列的最后一个记录的位置上，这个过程被称为一趟起泡排序。一个记录的位置上，这个过程被称为一趟起泡排序。 进行第二趟起泡排序，对序列表中前进行第二趟起泡排序，对序列表中前n-1个记录进行同样个记录进行同样的操作，使序列表中关键字次大的记录被交换到序列的的操作，使序列表中关键字次大的记录被交换到序列的n-1位置上；位置上； 对有对有n个记录的序列最多做个记录的序列最多做

24、n-1趟起泡就会把所有记录依趟起泡就会把所有记录依关键字大小排好序。如果在某一趟排序中都没有发生相关键字大小排好序。如果在某一趟排序中都没有发生相邻记录的交换，表示在该趟之前已达到排序的目的，整邻记录的交换，表示在该趟之前已达到排序的目的，整个排序过程可以结束。个排序过程可以结束。一、起泡排序一、起泡排序 假设在排序过程中，记录序列R1.n的状态为：第 i 趟起泡排序无序序列R1.n-i+1有序序列 Rn-i+2.nn-i+1无序序列R1.n-i有序序列 Rn-i+1.n比较相邻记录，将关关键字最大的记录键字最大的记录交换交换到 n-i+1 的位置上void BubbleSort(Elem R

25、 , int n) while (i 1) / while / BubbleSorti = n;i = lastExchangeIndex; / 本趟进行过交换的 / 最后一个记录的位置 if (Rj+1.key Rj.key) Swap(Rj, Rj+1); /iffor (j = 1; j i; j+)lastExchangeIndex = 1;lastExchangeIndex = j; /记下进行交换的记录位置注意注意: :2. 一般情况下，每经过一趟“起泡”，“i 减一”，但并不是每趟都如此。例如例如:523197825531579 89i=7i=6for (j = 1; j i;

26、j+) if (Rj+1.key Rj.key) 131. 起泡排序的结束条件为， 最后一趟没有进行最后一趟没有进行“交换记录交换记录”。jjjjjji=2jj时间分析时间分析: :最好情况（关键字在记录序列中顺序有序）：最好情况（关键字在记录序列中顺序有序）： 只需进行一趟起泡只需进行一趟起泡“比较比较”的次数：的次数：最坏情况（关键字在记录序列中逆序有序）：最坏情况（关键字在记录序列中逆序有序）： 需进行需进行n-1趟起泡趟起泡“比较比较”的次数：的次数：0“移动移动”的次数：的次数：“移动移动”的次数：的次数：n-12) 1() 1(2nnini2) 1(3) 1(32nnini二、一趟

27、快速排序二、一趟快速排序目标：目标：找一个记录，以它的关键字作为“枢枢轴轴”，凡其关键字小于枢轴关键字小于枢轴的记录均移动至该移动至该记录之前记录之前，反之凡关键字大于枢轴关键字大于枢轴的记录均移移动至该记录之后动至该记录之后。致使一趟排序一趟排序之后，记录的无序序列Rs.t将分分割成两部分割成两部分：Rs.i-1和Ri+1.t, 且 Rj.key Ri.key Rj.key (sji-1) 枢轴枢轴 (i+1jt)52 49 80 36 14 58 61 97 23 75stlowhigh设设 Rs=52 为枢轴暂存在为枢轴暂存在R0的位置上的位置上 将Rhigh.key和枢轴的关键字进行比

28、较，要求Rhigh.key枢轴的关键字 将Rlow.key和枢轴的关键字进行比较，要求Rlow.key枢轴的关键字high23low80high14low52例如例如R052lowhighhighhighlow 可见，经过“一次划分一次划分” ，将关键字序列 52, 49, 80, 36, 14, 58, 61, 97, 23, 75 调整为: 23, 49, 14, 36, (52) 58, 61, 97, 80, 75 在调整过程中，设立了两个指针: low和high，它们的初值分别为: s和t, 之后逐渐减小high，增加low，并保证 Rhigh.key52和Rlow.key52,否则

29、进行记录的“交换”。int Partition (SqList &L, int low, int high) / Partition L.r0 = L.rlow; pivotkey = L.rlow.key; /枢轴 while (lowhigh) while(low=pivotkey) - high; / 从右向左搜索L.rlow = L.rhigh;while (lowhigh & L.rlow.key=pivotkey) + low; / 从左向右搜索L.rhigh = L.rlow;L.rlow = L.r0; return low;三、快速排序三、快速排序 首先对无序

30、的记录序列进行“一次划一次划分分”，之后分别分别对分割所得两个子序列“递归递归”进行快速排序进行快速排序。无 序 的 记 录 序 列无序记录子序列(1)无序子序列(2)枢轴枢轴一次划分分别进行快速排序void QSort (SqList &L, int low, int high ) / 对记录序列Rs.t进行快速排序 if (low high) / 长度大于1 / QSortpivotloc = Partition(L, low, high); / 对 Rs.t 进行一次划分一次划分QSort(L, low, pivotloc-1); / 对低子序列递归排序，pivotloc是枢轴位

31、置是枢轴位置QSort(L, pivotloc+1, high); / 对高子序列递归排序void QuickSort( SqList & L) / 对顺序表进行快速排序 QSort(L, 1, L.length); / QuickSort 第一次调用函数 Qsort 时，待排序记录序列的上、下界分别为 1 和 L.length。【 例【 例 1 0 - 51 0 - 5 】 假 设 有】 假 设 有 8 8 个 记 录 ， 关 键 字 的 初 始 序 列 为个 记 录 ， 关 键 字 的 初 始 序 列 为45,34,67,95,78,12,26,45,34,67,95,78,12,

32、26,4545，用快速排序法进行排序。，用快速排序法进行排序。【解】（【解】（1 1）一趟快速排序过程如图）一趟快速排序过程如图10-510-5所示：所示：51 4545 3434 6767 9595 7878 1212 2626 4545 初始关键字序列初始关键字序列 j j 向前搜索向前搜索 i i j j 2626 3434 6767 9595 7878 1212 4545 第一次交换后第一次交换后 i i j j i i 向后搜索向后搜索 2626 3434 6767 9595 7878 1212 4545 i j j 第二次交换后第二次交换后 2626 3434 9595 7878

33、1212 6767 4545 i i j j 第三次交换后第三次交换后 2626 3434 1212 9595 7878 6767 4545 i i j j 2626 3434 1212 7878 9595 6767 4545 2626 3434 1212 4545 7878 9595 6767 4545 第四次交换后第四次交换后 j j 向前扫描向前扫描 i i i i j j j j j j j 图图10-5 一趟快速排序过程一趟快速排序过程 演示52（2 2）各趟排序之后的结果）各趟排序之后的结果 2626 3434 1212 4545 4545 3434 6767 9595 7878

34、1212 2626 4545 初始关键字序列初始关键字序列 6767 9595 7878 4545 6767 9595 7878 4545 6767 9595 7878 4545 9595 4545 2626 3434 9595 7878 1212 6767 4545 9595 7878 6767 4545 7878 6767 4545 7878 9595 6767 4545 2626 3434 1212 4545 2626 3434 1212 4545 2626 3434 1212 4545 2626 3434 1212 4545 2626 3434 1212 4545 2626 3434

35、1212 4545 6767 9595 7878 4545 （1 1） （2 2） （3 3） （4 4） （5 5） （6 6） （7 7） （8 8） 图图10-6 10-6 快速排序过程快速排序过程 演示53四、快速排序的时间分析四、快速排序的时间分析假设一次划分所得枢轴位置i=k，则对n个记录进行快排所需时间其中 Tpass(n)为对n个记录进行一次划分所需时间 若待排序列中记录的关键字是随机分布的，则k取1至n中任意一值的可能性相同。T(n) = Tpass(n) + T(k-1) + T(n-k)nkavgavgavgknTkTnCnnT1)()1(1)(设 Tavg(1)b则可得

36、结果:)1ln()1)(22()(nncbnTavg结论结论: 快速排序的时间复杂度为快速排序的时间复杂度为O(nlogn)由此可得快速排序所需时间的平均值为： 若待排记录的初始状态为按关键字有序时，若待排记录的初始状态为按关键字有序时，快速排序将蜕化为起泡排序快速排序将蜕化为起泡排序，其时间复杂度为O(n2)。 为避免出现这种情况，需在进行一次划分之前，进行“予处理予处理”，即： 先对R(s).key，R(t).key和R(s+t)/2.key，进行相互比较，然后取取关键字为“三者之中三者之中”的记录为枢轴为枢轴记录。 在算法实现中需设置一个栈的存贮空间来实现递归，栈的在算法实现中需设置一个

37、栈的存贮空间来实现递归，栈的大小取决于递归深度，最多不会超过大小取决于递归深度，最多不会超过n。若每次都选较长的分若每次都选较长的分组序列进栈，而处理较短的分组序列，则递归深度最多不会组序列进栈，而处理较短的分组序列，则递归深度最多不会超过超过log2n，因此快速排序需要的辅助存贮空间为因此快速排序需要的辅助存贮空间为O(log2n)。 快速排序算法是不稳定排序，对于有相同关键字的记录，快速排序算法是不稳定排序，对于有相同关键字的记录，排序后有可能颠倒位置。排序后有可能颠倒位置。 5710.4 选择选择 排排 序序简简 单单 选选 择择 排排 序序堆堆 排排 序序一、简单选择排序一、简单选择排

38、序假设排序过程中，待排记录序列的状态为：有序序列R1.i-1无序序列 Ri.n 第 i 趟简单选择排序从中选出关键字最小的记录有序序列R1.i无序序列 Ri+1.n(3)不断重复过程不断重复过程(1)和和(2)，就不断地从待排记录序列中剩下的，就不断地从待排记录序列中剩下的(n-1，n-2，2)个记录中选出关键字最小的记录与该区第个记录中选出关键字最小的记录与该区第1位位置的记录交换，然后把第置的记录交换，然后把第1位置的记录不断位置的记录不断“插入插入”已排序记已排序记录序列之后。经过录序列之后。经过n-1次的选择和多次交换后，次的选择和多次交换后，R1 Rn就排成了就排成了有序序列，整个排

39、序过程结束。具有有序序列，整个排序过程结束。具有n个记录的待排记录序列个记录的待排记录序列要做要做n-1次的选择和交换才能成为有序表。次的选择和交换才能成为有序表。 (1)每次从待排记录序列中选出关键字最小的记录；每次从待排记录序列中选出关键字最小的记录； (2)将它与待排记录序列第一位置的记录交换后，再将其将它与待排记录序列第一位置的记录交换后，再将其“插插入入”已排序记录序列已排序记录序列(初始为空初始为空)；60void SelectSort(SqList &L) for(i=1;i n/2的结点的结点Ri都没都没有孩子结点，因此以有孩子结点，因此以Ri为根的子树已经是堆。为根的

40、子树已经是堆。71 从从i= n/2的结点的结点Ri开始，比较根结点与左、右孩子的开始，比较根结点与左、右孩子的关键字，若根结点的值小于左、右孩子中的较小者，则关键字，若根结点的值小于左、右孩子中的较小者，则交换根结点和值较小孩子的位置交换根结点和值较小孩子的位置，即把根结点下移，然，即把根结点下移，然后根结点继续和新的孩子结点比较，如此一层一层地递后根结点继续和新的孩子结点比较，如此一层一层地递归下去，直到根结点下移到某一位置时，它的归下去，直到根结点下移到某一位置时，它的左、右子左、右子结点的值都大于它的值或者已成为叶子结点结点的值都大于它的值或者已成为叶子结点。这个过程。这个过程称为称为

41、“筛选筛选”。 从一个无序序列建堆的过程就是一个从一个无序序列建堆的过程就是一个反复反复“筛选筛选”的过的过程，程，“筛选筛选”需要从需要从i= n/2的结点的结点Ri开始，直至结点开始，直至结点R1结束。结束。72例如例如有一个有一个8个元素的无序序列个元素的无序序列56,37,48,24,61,05, 16,37，它所对应的完全二叉树及其建堆过程如图，它所对应的完全二叉树及其建堆过程如图10-9所示。所示。因为因为n=8，n/2=4，所以从第所以从第4个结点起至第一个结个结点起至第一个结点止，依次对每一个结点进行点止，依次对每一个结点进行“筛选筛选”。735637482461051637i

42、=45637482461051637i=3(a)2437不调整不调整 (b)4805 48沿左子树下移一层沿左子树下移一层 建堆过程示例建堆过程示例 74(对对i=4的结点筛选的结点筛选) (对对i=3的结点筛选的结点筛选) 5637052461481637i=25624053761481637i=1(c) 3724 37沿左子树下移一层沿左子树下移一层 (d) 5605 56沿右子树下移一层沿右子树下移一层 0524563761481637i=2i+10524163761485637(对对i=2的结点筛选的结点筛选) (对对i=1的结点筛选的结点筛选) (e) 5616 56沿右子树继续下移

43、一层沿右子树继续下移一层 (f) 比较调整结束比较调整结束 堆建好堆建好 75建堆是一个从下往上进行建堆是一个从下往上进行“筛选筛选”的过程。的过程。40554973816436122798例如例如: 排序之前的关键字序列为123681734998817355 现在，左/右子树都已经调整为堆，最后只要调整根结点，使整个二叉树是个“堆”即可。98494064361227void HeapSort(HeapType &H) /对记录序列对记录序列R1.n进行堆排序进行堆排序 for (i=H.length/2;i0; - i) /循环建立初始堆循环建立初始堆 HeapAdjust(H,i,

44、H.length); /建大顶堆建大顶堆 for (i=H.length;i1; - i) /*进行进行n-1次循环次循环,完成推排序完成推排序*/ H.r1 H.ri; /将堆顶记录和当前未经排序子序列将堆顶记录和当前未经排序子序列H.r1.i中中 /最后最后一个记录进行交换一个记录进行交换 HeapAdjust(H,1, i-1); /将将H.r1.i-1重新调整为大顶堆重新调整为大顶堆/ HeapSort77void HeapAdjust(HeapType &H,int s,int m)/s为下界，为下界，m为上界为上界 / H.r记录序列从第二个开始满足堆的特性记录序列从第二个

45、开始满足堆的特性 rc=H.rs; for(j=2*s;j=m;j*2) if (jm & LT(H.rj.key, H.rj+1.key) + j; if (!LT(rc.key, L.rj.key) break;/rc应插入在应插入在s上上 H.rs=H.rj; s=j; H.rs=rc; /插入插入/ HeapAdjust调整堆的算法：调整堆的算法：7898814973556412362740例如例如:是大顶堆是大顶堆12但在 98 和 12 进行互换之后，它就不不是堆了因此，需要对它进行“筛选”98128173641298比较比较比较【例【例10-7】用】用“筛选法筛选法”在如

46、图在如图10-9(f)的堆中进行排序。的堆中进行排序。【解】调用筛选运算进行堆排序的过程如图【解】调用筛选运算进行堆排序的过程如图10-10(a)(n)所示。所示。 05241637614856372416376148563705（a）初始堆初始堆 （b）交换交换05和和37 24376148563716052437614837165605（c） 重建堆，筛选重建堆，筛选37下移一层下移一层 （d）交换交换16和和56 8061483716055624376137160556243748（e） 重建堆，筛选重建堆，筛选56下移两层下移两层 （f）交换交换24和和48 0556243737481

47、6616105562437374816（g） 重建堆，筛选重建堆，筛选48下移一层下移一层 （h）交换交换37和和61 8105562437374816610524374816613756（i） 重建堆，筛选重建堆，筛选61下移一层下移一层 （j） 交换交换37和和56 0524371661375648（k）重建堆，筛选重建堆，筛选56下移一层下移一层 0524371637564861（l） 交换交换48和和61 8205243716375648610524371637564861（m） 重建堆，筛选重建堆，筛选61下移一层下移一层 （n） 交换交换56和和61 堆排序示例堆排序示例 83 堆

48、排序所需的记录移动的总次数为堆排序所需的记录移动的总次数为O(nlogn)，因此堆因此堆排序的最坏时间复杂度为排序的最坏时间复杂度为O(nlogn)。堆排序一般适合堆排序一般适合于待排序记录数比较多的情况。于待排序记录数比较多的情况。 堆排序需要一个辅助空间，所以空间复杂度为堆排序需要一个辅助空间，所以空间复杂度为O(1)。 堆排序也是不稳定排序。堆排序也是不稳定排序。 84性能分析性能分析10.5 归归 并并 排排 序序归并排序的过程基于下列基本思想基本思想： 将两个或两个以上的有序子序列 “归并” 为一个有序序列。在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻位置相邻的记录有

49、序子序列归并为一个一个记录的有序序列。有有 序序 序序 列列 Rl.n有序子序列有序子序列 Rl.m有序子序列有序子序列 Rm+1.n这个操作对顺序表轻而易举。void Merge (RcdType SR, RcdType &TR, int i, int m, int n) / 将有序的记录序列 SRi.m 和 SRm+1.n / 归并为有序的记录序列 TRi.n / Mergefor (j=m+1, k=i; i=m & j=n; +k) / 将SR中记录由小到大地并入TR if (SRi.key=SRj.key) TRk = SRi+; else TRk = SRj+; i

50、f (i=m) TRk.n = SRi.m; / 将剩余的 SRi.m 复制到 TRif (j=n) TRk.n = SRj.n; / 将剩余的 SRj.n 复制到 TRvoid Msort(RcdType SR, RcdType &TR1, int s, int t) / 将SRs.t 归并排序为 TR1s.t if (s=t) TR1s=SRs; else / Msort m = (s+t)/2; / 将SRs.t平分为SRs.m和SRm+1.tMsort(SR, TR2, s, m); / 递归地将SRs.m归并为有序的TR2s.mMsort(SR, TR2, m+1, t);

51、/递归地SRm+1.t归并为有序的TR2m+1.tMerge(TR2, TR1, s, m, t); / 将TR2s.m和TR2m+1.t归并到TR1s.tvoid MergeSort (SqList &L) / 对顺序表 L 作2-路归并排序。 MSort(L.r, L.r, 1, L.length); / MergeSort容易看出，对n个记录进行归并排序的时间复杂度为(nlogn)。即： 每一趟归并的时间复杂度为O(n)， 总共需进行log2n趟。【例【例10-8】初始序列为】初始序列为23，56，42，37，15，84，72，27，18用二路归并排序法排序。用二路归并排序法排序

52、。【解】排序后的结果为：【解】排序后的结果为：15，18，23，27，37，42，56，72，84，整个归并过程如图，整个归并过程如图10-12所示。所示。 92图图 10-12 归并排序示例归并排序示例 2323，5656，4242，3737，1515，8484，7272，2727，1818 2323，5656，4242，3737，1515|8484，7272，2727，1818 2323，5656，42423737，1515|8484，72722727，1818 2323，5656424237371515|8484727227271818 23562356423715|8472271842

53、3715|8472271823,56 23,56 4215,37 |72, 84 18 ,274215,37 |72, 84 18 ,27 23, 23, 4242 ,56 ,5615,37 |18 ,27,72, 8415,37 |18 ,27,72, 84 15, 15, 23,23,3737, ,4242,56 ,56 |18 ,27,72, 84|18 ,27,72, 84 15,18,15,18,23,23,27,3727,37, ,4242,56,56,72,8472,84 93例如：例如：52, 23, 80, 36, 68, 14 (s=1, t=6) 52, 23, 80 3

54、6, 68, 14 52, 23 80 52 23, 52 23, 52, 8036, 68 143636, 6814, 36, 68 14, 23, 36, 52, 68, 80 23 52 23 36 68 801468基数排序借助于基数排序借助于“多关键字排序多关键字排序”的思想来的思想来实现实现“单关键字排序单关键字排序”，即先将每个记录分，即先将每个记录分解成若干部分，然后通过对各部分关键字的解成若干部分，然后通过对各部分关键字的分别排序，最终完成对全部记录的排序。分别排序，最终完成对全部记录的排序。95一、多关键字的排序一、多关键字的排序n个记录的序列个记录的序列R1，R2，Rn对

55、关键字对关键字( Ki 0, Ki 1, Ki d-1)有序指：有序指：对序列中任意两个记录对序列中任意两个记录Ri和和Rj(1 i j )都满足下列都满足下列(词典词典)有序关系：有序关系： ( Ki 0, Ki 1, Ki d-1)( Kj 0, Kj 1, Kj d-1)其中其中K0被称为被称为“最主最主”位关键字，位关键字，Kd-1被称为被称为“最最次次”位关键字。位关键字。96多关键字排序的两种作法：多关键字排序的两种作法： 最高位优先最高位优先MSD法：法：先对先对K0进行排序，并按进行排序，并按K0的不同的不同值将记录序列分成若干子序列之后，分别对值将记录序列分成若干子序列之后，

56、分别对K1进行排进行排序，序，依次类推，直至最后对最次位关键字排序完，依次类推，直至最后对最次位关键字排序完成为止。成为止。 最低位优先最低位优先LSD法：法：先对先对Kd-1进行排序，然后对进行排序，然后对Kd-2进进行排序，行排序，依次类推，直至最后对最主位关键字排，依次类推，直至最后对最主位关键字排序完成为止。排序过程中不需要根据序完成为止。排序过程中不需要根据“前一个前一个”关键字关键字的排序结果，将记录序列分割成若干个的排序结果，将记录序列分割成若干个(“前一个前一个”关关键字不同的键字不同的)子序列。子序列。97例：学生记录含三个关键字：系别、班号和班内的序列号，例：学生记录含三个

57、关键字：系别、班号和班内的序列号，其中以系别为最主位关键字。其中以系别为最主位关键字。最低位优先最低位优先LSD法的排序过法的排序过程如下：程如下：无序序列 3,2,30 1,2,15 3,1,20 2,3,18 2,1,20 对K2排序排序 1,2,15 2,3,18 3,1,20 2,1,20 3,2,30对K1排序排序 3,1,20 2,1,20 1,2,15 3,2,30 2,3,18对K0排序排序 1,2,15 2,1,20 2,3,18 3,1,20 3,2,30 98二、链式基数排序二、链式基数排序 假如多关键字的记录序列中，每个关键字的假如多关键字的记录序列中，每个关键字的取值

58、范围相同，则按取值范围相同，则按LSD法进行排序时，可以法进行排序时，可以采用采用“分配分配-收集收集”的方法；其好处是不需要进的方法；其好处是不需要进行关键字间的比较。行关键字间的比较。 对于数字型或字符型的单关键字，可以看对于数字型或字符型的单关键字，可以看成是由多个数位或多个字符构成的多关键字，成是由多个数位或多个字符构成的多关键字，此时可以采用这种此时可以采用这种“分配分配-收集收集”的办法进行排的办法进行排序，称作基数排序法。序，称作基数排序法。99【例【例10-9】设待排序序列中有】设待排序序列中有9个记录，其关键字分个记录，其关键字分别别209，386，768，185，247，6

59、06，230，834，539，使用基数排序法进行排序。使用基数排序法进行排序。【解】首先按其【解】首先按其“个位数个位数”取值分别为取值分别为0，1，9“分配分配”成成10组，之后按从组，之后按从0至至9的顺序将它们的顺序将它们“收收集集”在一起；然后按其在一起；然后按其“十位数十位数”取值分别为取值分别为0，1，9“分配分配”成成10组，之后再按从组，之后再按从0至至9的顺序的顺序将它们将它们“收集收集”在一起；最后按其在一起；最后按其“百位数百位数”重复重复一遍上述操作，便可得到这组关键字的有序序列。一遍上述操作，便可得到这组关键字的有序序列。100在计算机上实现基数排序时，为减少所需辅助

60、存储空间，应采用链表作存储结构，即链式基数排序，具体作法为： 待排序记录以指针相链，构成一个链表；“分配”时，按当前“关键字位”所取值，将记录分配到不同的“链队列”中，每个队列中记录的 “关键字位”相同；“收集”时，按当前关键字位取值从小到大将各队列首尾相链成一个链表;对每个关键字位均重复2) 和3) 两步。例：p369367167239237138230139进行第一次分配进行第一次分配进行第一次收集进行第一次收集f0 r0f7 r7f8 r8f9 r9p230230367 167237367167237138368239139369 239139138进行第二次分配进行第二次分配p230237138239139p230367167237138368239139f3 r3f6 r6230 23713823913