哈工大数据结构10

1、第第10章章 排序排序10.1 概述概述1.1.排序（排序（SortingSorting） 将数据元素（或记录）的任意序列，重新排列成一个按关键将数据元素（或记录）的任意序列，重新排列成一个按关键字有序（递增或递减）的序列的过程称为排序。字有序（递增或递减）的序列的过程称为排序。2.2. 排序过程中的两种基本操作排序过程中的两种基本操作（1 1）比较两个关键字值的大小。）比较两个关键字值的大小。（2 2）根据比较结果，移动记录的位置。）根据比较结果，移动记录的位置。3.3.对关键字排序的三个原则对关键字排序的三个原则 （1 1）关键字值为数值型的，则按键值大小为依据。）关键字值为数值型的，则按

2、键值大小为依据。 （2 2）关键字值为）关键字值为ASCIIASCII码，则按键值的内码编排顺序为依据。码，则按键值的内码编排顺序为依据。 （3 3）关键字值为汉字字符串类型，则大多以汉字拼音的字典次）关键字值为汉字字符串类型，则大多以汉字拼音的字典次序为依据。序为依据。4.4.排序方法的稳定和不稳定排序方法的稳定和不稳定 若对任意的数据元素序列，使用某个排序方法按关键字进若对任意的数据元素序列，使用某个排序方法按关键字进行排序，对原先具有相同键值元素间的位置关系，若排序前与行排序，对原先具有相同键值元素间的位置关系，若排序前与排序后保持一致，称此排序方法是稳定的；反之，则称为不稳排序后保持一

3、致，称此排序方法是稳定的；反之，则称为不稳定的。定的。例：对数据键值为：例：对数据键值为：5 5，3 3，8 8，3 3，6 6，6 6，排序。，排序。 若排序后的序列为：若排序后的序列为：3 3，3 3，5 5，6 6，6 6，8 8 其相同键值的元素位置依旧是其相同键值的元素位置依旧是 3 3 在在 3 3 前，前，6 6 在在 6 6 前，前，与排序前保持一致，则这种排序法是稳定的。与排序前保持一致，则这种排序法是稳定的。 若排序后的序列为：若排序后的序列为：3 3，3 3，5 5，6 6，6 6，8 8则这种排序法是不稳定的。则这种排序法是不稳定的。5 5待排序记录的三种存储方式待排序

4、记录的三种存储方式 （1 1）待排序记录存放在地址连续的一组存储单元上。）待排序记录存放在地址连续的一组存储单元上。 （2 2）待排序记录存放在静态链表中。）待排序记录存放在静态链表中。 （3 3）待排序记录存放在一组地址连续的存储单元，同时另设）待排序记录存放在一组地址连续的存储单元，同时另设一个指示各个记录存储位置的地址向量，在排序过程中不移动一个指示各个记录存储位置的地址向量，在排序过程中不移动记录本身，而移动地址向量中这些记录的记录本身，而移动地址向量中这些记录的“地址地址”，在排序结，在排序结束后，再按照地址向量中的值调整记录的存储位置。束后，再按照地址向量中的值调整记录的存储位置。

5、 6 6内排序内排序 整个排序过程都在内存进行的排序称为内排序。整个排序过程都在内存进行的排序称为内排序。7 7外排序外排序 待排序的数据元素量大，以致内存一次不能容纳全部记录，待排序的数据元素量大，以致内存一次不能容纳全部记录，在排序过程中需要对外存进行访问的排序称为外排序。在排序过程中需要对外存进行访问的排序称为外排序。本章只讨论内排序。本章只讨论内排序。10.2 插入排序插入排序取要插入的元素，直接插在一个有序序列的合适位置。取要插入的元素，直接插在一个有序序列的合适位置。1.1.直接插入排序直接插入排序012362410612345基本思想：基本思想： 直接插入排序是一种最简单的排序方

6、法，它的基本操直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插到已排序好的有序表中，从而得到一个作是将一个记录插到已排序好的有序表中，从而得到一个新的，记录数增新的，记录数增 1 1 的有序表。的有序表。 整个排序过程为整个排序过程为 n-1 趟插入，即先将序列中第趟插入，即先将序列中第 1 个记个记录看成是一个有序子序列，然后从第录看成是一个有序子序列，然后从第 2 个记录开始，逐个个记录开始，逐个进行插入，直至整个序列有序进行插入，直至整个序列有序。排序过程：排序过程：将第一个元素将第一个元素 r1 作为已排序有序序列；作为已排序有序序列；其他元素其他元素r2,r3,r4,r

7、5,.rn作为未排序序列；作为未排序序列；循环：循环：从未排序序列中依次取一个元素；（循环从从未排序序列中依次取一个元素；（循环从i=2,3,4,5.）取一个元素后进行判断：取一个元素后进行判断：如果所取元素小于当前有序序列的序尾，则：如果所取元素小于当前有序序列的序尾，则：（1 1）将所取）将所取元素赋值给元素赋值给r0， r0 当作哨兵。当作哨兵。（2 2）循环：）循环： 在当前有序序列中寻找自己的位置，进行插入：在当前有序序列中寻找自己的位置，进行插入： 从当前有序序列的序尾开始，倒着往前，将哨兵与相应元素逐个比较：从当前有序序列的序尾开始，倒着往前，将哨兵与相应元素逐个比较： 哨兵比当

8、前元素小，当前元素就往后移一个位置；再往前比，若哨哨兵比当前元素小，当前元素就往后移一个位置；再往前比，若哨 兵比当前元素还小，当前元素再往后移一个位置兵比当前元素还小，当前元素再往后移一个位置 . .直到哨兵大于直到哨兵大于 等于当前元素，循环结束，将哨兵插入到当前元素的后面。等于当前元素，循环结束，将哨兵插入到当前元素的后面。如果如果所取元素大于等于有序序列的序尾，则保持原存储位置不变。所取元素大于等于有序序列的序尾，则保持原存储位置不变。e.g: 36、24、10、6、12存放在存放在 r 数组的下标为数组的下标为 1 至至 5 的元素之中，用直接插入法将的元素之中，用直接插入法将 其排

9、序。结果仍保存在下标为其排序。结果仍保存在下标为 1 至至 5 的元素之中。的元素之中。1、直接插入排序、直接插入排序012362410612345362424ie.g: 36、24、10、6、12存放在存放在 r 数组的下标为数组的下标为 1 至至 5 的元素之中，用直接插入法将的元素之中，用直接插入法将 其排序。结果仍保存在下标为其排序。结果仍保存在下标为 1 至至 5 的元素之中。的元素之中。1、直接插入排序、直接插入排序0123624106123453624ie.g: 36、24、10、6、12存放在存放在 r 数组的下标为数组的下标为 1 至至 5 的元素之中，用直接插入法将的元素之

10、中，用直接插入法将 其排序。结果仍保存在下标为其排序。结果仍保存在下标为 1 至至 5 的元素之中。的元素之中。1、直接插入排序、直接插入排序0123624106123453624i24e.g: 36、24、10、6、12存放在存放在 r 数组的下标为数组的下标为 1 至至 5 的元素之中，用直接插入法将的元素之中，用直接插入法将 其排序。结果仍保存在下标为其排序。结果仍保存在下标为 1 至至 5 的元素之中。的元素之中。1、直接插入排序、直接插入排序0123624106123453610i2410e.g: 36、24、10、6、12存放在存放在 r 数组的下标为数组的下标为 1 至至 5 的

11、元素之中，用直接插入法将的元素之中，用直接插入法将 其排序。结果仍保存在下标为其排序。结果仍保存在下标为 1 至至 5 的元素之中。的元素之中。1、直接插入排序、直接插入排序0123624106123453610i24e.g: 36、24、10、6、12存放在存放在 r 数组的下标为数组的下标为 1 至至 5 的元素之中，用直接插入法将的元素之中，用直接插入法将 其排序。结果仍保存在下标为其排序。结果仍保存在下标为 1 至至 5 的元素之中。的元素之中。1、直接插入排序、直接插入排序0123624106123453610i24e.g: 36、24、10、6、12存放在存放在 r 数组的下标为数

12、组的下标为 1 至至 5 的元素之中，用直接插入法将的元素之中，用直接插入法将 其排序。结果仍保存在下标为其排序。结果仍保存在下标为 1 至至 5 的元素之中。的元素之中。1、直接插入排序、直接插入排序0123624106123453610i2410e.g: 36、24、10、6、12存放在存放在 r 数组的下标为数组的下标为 1 至至 5 的元素之中，用直接插入法将的元素之中，用直接插入法将 其排序。结果仍保存在下标为其排序。结果仍保存在下标为 1 至至 5 的元素之中。的元素之中。1、直接插入排序、直接插入排序01236241061234536246i106e.g: 36、24、10、6、

13、12存放在存放在 r 数组的下标为数组的下标为 1 至至 5 的元素之中，用直接插入法将的元素之中，用直接插入法将 其排序。结果仍保存在下标为其排序。结果仍保存在下标为 1 至至 5 的元素之中。的元素之中。1、直接插入排序、直接插入排序01236241061234536246i10e.g: 36、24、10、6、12存放在存放在 r 数组的下标为数组的下标为 1 至至 5 的元素之中，用直接插入法将的元素之中，用直接插入法将 其排序。结果仍保存在下标为其排序。结果仍保存在下标为 1 至至 5 的元素之中。的元素之中。1、直接插入排序、直接插入排序01236241061234536246i10

14、e.g: 36、24、10、6、12存放在存放在 r 数组的下标为数组的下标为 1 至至 5 的元素之中，用直接插入法将的元素之中，用直接插入法将 其排序。结果仍保存在下标为其排序。结果仍保存在下标为 1 至至 5 的元素之中。的元素之中。1、直接插入排序、直接插入排序01236241061234536246i10e.g: 36、24、10、6、12存放在存放在 r 数组的下标为数组的下标为 1 至至 5 的元素之中，用直接插入法将的元素之中，用直接插入法将 其排序。结果仍保存在下标为其排序。结果仍保存在下标为 1 至至 5 的元素之中。的元素之中。1、直接插入排序、直接插入排序0123624

15、1061234536246i106e.g: 36、24、10、6、12存放在存放在 r 数组的下标为数组的下标为 1 至至 5 的元素之中，用直接插入法将的元素之中，用直接插入法将 其排序。结果仍保存在下标为其排序。结果仍保存在下标为 1 至至 5 的元素之中。的元素之中。1、直接插入排序、直接插入排序0123624106345362412i1061212e.g: 36、24、10、6、12存放在存放在 r 数组的下标为数组的下标为 1 至至 5 的元素之中，用直接插入法将的元素之中，用直接插入法将 其排序。结果仍保存在下标为其排序。结果仍保存在下标为 1 至至 5 的元素之中。的元素之中。1

16、、直接插入排序、直接插入排序0123624106345362412i10612e.g: 36、24、10、6、12存放在存放在 r 数组的下标为数组的下标为 1 至至 5 的元素之中，用直接插入法将的元素之中，用直接插入法将 其排序。结果仍保存在下标为其排序。结果仍保存在下标为 1 至至 5 的元素之中。的元素之中。1、直接插入排序、直接插入排序0123624106345362412i10612e.g: 36、24、10、6、12存放在存放在 r 数组的下标为数组的下标为 1 至至 5 的元素之中，用直接插入法将的元素之中，用直接插入法将 其排序。结果仍保存在下标为其排序。结果仍保存在下标为

17、1 至至 5 的元素之中。的元素之中。1、直接插入排序、直接插入排序0123624106345362412i1061212算法：算法：void Insertsort() for( i=2;i=L;i+ ) / 依次插入依次插入r2,r3,rn if ( ri.keyri-1.key ) r0=ri; / 置监视哨置监视哨 j=i-1; while(r0.key275653275，在后半区继续找；，在后半区继续找； （2 2）再与后半区中间位置的关键字比较，）再与后半区中间位置的关键字比较，653512653512，再，再继续在后半区找；继续在后半区找； （3 3）再与后半区中间位置的关键字比较

18、，）再与后半区中间位置的关键字比较，653897653897，经，经三次比较找到插入位置，然后插入三次比较找到插入位置，然后插入653653。算法：算法：void BInsSort() for(i=2;i=n;i+) r0=ri; / 将将ri 暂存到暂存到r0 while(lowhigh时，循环结束，大致插入位置已确定。时，循环结束，大致插入位置已确定。 m=(low+high)/2; / 折半折半 if(r0.key=high+1;- -j) rj+1=rj; / 记录后移，直到空出记录后移，直到空出 rhigh+1为止为止 rhigh+1=r0; / 插入插入 二分插入排序辅助空间和直接

19、插入相同，为二分插入排序辅助空间和直接插入相同，为O (1 1) 。 从时间上比较，二分插入仅减少了比较次数，而记录从时间上比较，二分插入仅减少了比较次数，而记录的移动次数不变，时间复杂度仍为的移动次数不变，时间复杂度仍为O(n(n2 2) )。 二分插入排序是稳定的排序方法。二分插入排序是稳定的排序方法。3.3.希尔排序希尔排序(Shells Sort) 希尔排序又称希尔排序又称“缩小增量排序缩小增量排序”，它也是一种插入排序方法，它也是一种插入排序方法，但在时间上较前两种排序方法有较大的改进。但在时间上较前两种排序方法有较大的改进。基本思想：基本思想： 先将先将整个待排序记录序列整个待排序

20、记录序列分割成若干分割成若干子序列子序列分别进行分别进行直接直接插入排序插入排序，待整个序列中的记录，待整个序列中的记录“基本有序时基本有序时”，再对全体记录，再对全体记录进行一次直接插入排序。进行一次直接插入排序。 特点：特点： 子序列不是简单的逐段分割，而是将相隔某个子序列不是简单的逐段分割，而是将相隔某个“增量增量”的记录的记录组成一个子序列，组成一个子序列， 所以关键字较小的记录不是一步一步地前移，所以关键字较小的记录不是一步一步地前移，而是跳跃式前移，从而使得在进行最后一趟增量为而是跳跃式前移，从而使得在进行最后一趟增量为 1 的插入排序的插入排序时，序列已基本有序，只要做少量比较和

21、移动即可完成排序，时时，序列已基本有序，只要做少量比较和移动即可完成排序，时间复杂度较低。间复杂度较低。排序过程：排序过程： 先取一个正整数先取一个正整数 d1n d1n ，把所有相隔把所有相隔 d1 d1 的记录放一组，的记录放一组，组内进行直接插入排序；然后取组内进行直接插入排序；然后取 d2d1d20) for ( i=gap+1; i0) if ( rjrj+gap ) / 对子序列作直接插入排序对子序列作直接插入排序 x=rj; rj=rj+gap; rj+gap=x; j=j-gap; else j=0; gap=gap/2; / 每次减半每次减半,直至步长为直至步长为 1 效率分

22、析：效率分析： 希尔排序可提高排序速度：希尔排序可提高排序速度： 分组后分组后 n n 值减小，值减小，nn更小。更小。在大量实验基础上可推出：当在大量实验基础上可推出：当 n n 在某在某 个特定范围内希尔排序所需的比较和移动次数约为个特定范围内希尔排序所需的比较和移动次数约为 n n1.3 1.3 , , 所以其所以其平均时平均时 间复杂度约为间复杂度约为O( nO( n1.31.3) )。其其辅助空间为辅助空间为O(1)O(1)。 关键字较小的记录跳跃式前移，在进行最后一趟增量为关键字较小的记录跳跃式前移，在进行最后一趟增量为 1 1 的插入排的插入排 序时，序列已基本有序。序时，序列已

23、基本有序。 希尔排序为不稳定排序。希尔排序为不稳定排序。 增量序列取法：增量序列取法： 没有除没有除1 1以外的公因子。以外的公因子。 最后一个增量值必须为最后一个增量值必须为1 1。10.3 快速排序法快速排序法1.1.冒泡排序冒泡排序基本思想：基本思想： 冒泡法也称沉底法，每相邻两个记录关键字比大小，大的冒泡法也称沉底法，每相邻两个记录关键字比大小，大的记录往下沉（即较小的往上浮）。每一趟把最后一个下沉的位记录往下沉（即较小的往上浮）。每一趟把最后一个下沉的位置记下，下一趟只需检查比较到此为止；到所有记录都不发生置记下，下一趟只需检查比较到此为止；到所有记录都不发生下沉时，整个过程结束。下

24、沉时，整个过程结束。排序过程：排序过程： 将第一个记录的关键字与第二个记录的关键字进行比将第一个记录的关键字与第二个记录的关键字进行比较，若为逆序较，若为逆序r1.keyr2.keyr1.keyr2.key，则交换；然后比较第二则交换；然后比较第二个记录与第三个记录；依次类推，直至个记录与第三个记录；依次类推，直至用用n-1n-1次比较完成次比较完成 n n个记录个记录的的第一趟冒泡排序第一趟冒泡排序，结果关键字，结果关键字最大最大的记录被安置的记录被安置在最后一个记录上。在最后一个记录上。 对前对前n-1n-1个记录进行第二趟冒泡排序，结果使关键字个记录进行第二趟冒泡排序，结果使关键字次次大

25、大的记录被安置在第的记录被安置在第n-1n-1个记录位置。个记录位置。 重复上述过程，直到重复上述过程，直到“在一趟排序过程中没有可进行在一趟排序过程中没有可进行记录交换的操作记录交换的操作”为止。为止。例例49 38 65 97 76 13 27 30 初始关键字初始关键字38 49 65 76 13 27 30 97 第一趟第一趟38 49 65 13 27 30 76 第二趟第二趟38 49 13 27 30 65 第三趟第三趟38 13 27 30 49 第四趟第四趟13 27 30 38 第五趟第五趟384976971397279730971376767627301365276530

26、651313494930492738273830381 2 3 4 5 6 7 8算法：算法：void Bubblesort() for(i=1;iL;i+) for(j=1;jRj+1.key ) / / 大则交换大则交换 R0.key=Rj.key; Rj.key=Rj+1.key; Rj+1.key=R0.key; 效率分析：效率分析： 空间效率：仅用了一个辅助单元，空间效率：仅用了一个辅助单元，空间复杂度为空间复杂度为O O（1 1）。）。 时间效率：总共要进行时间效率：总共要进行n-1n-1趟冒泡，对趟冒泡，对j j个记录的表进行一趟冒个记录的表进行一趟冒泡需要泡需要j-1j-1次关

27、键字的比较。次关键字的比较。 移动次数：移动次数： 最好情况下：待排序列已有序，不需移动。最好情况下：待排序列已有序，不需移动。 最坏情况下：每次比较后均要进行三次移动。最坏情况下：每次比较后均要进行三次移动。 移动次数移动次数= = 时间复杂度为时间复杂度为: : O O（n n2 2） 冒泡排序是一种稳定排序。冒泡排序是一种稳定排序。) 1(21) 1(2nnjnj总比较次数)1(23)1(32nnjnj 2. 2.快速排序快速排序基本思想：基本思想： 就排序时间而言，快速排序被认为是一种最好的内部排序方法。就排序时间而言，快速排序被认为是一种最好的内部排序方法。 通过一趟快速排序将待排序

28、的记录分割成独立的两部分，其中前一部分通过一趟快速排序将待排序的记录分割成独立的两部分，其中前一部分记录的关键字均比枢轴记录的关键字小；后一部分记录的关键字均比枢轴记记录的关键字均比枢轴记录的关键字小；后一部分记录的关键字均比枢轴记录的关键字大，枢轴记录得到了它在整个序列中的最终位置并被存放好，这录的关键字大，枢轴记录得到了它在整个序列中的最终位置并被存放好，这个过程称为一趟快速排序。个过程称为一趟快速排序。 第二趟再分别对分割成两部分子序列，再进行快速排序，这两部分子序第二趟再分别对分割成两部分子序列，再进行快速排序，这两部分子序列中的枢轴记录也得到了最终在序列中的位置而被存放好，并且它们又

29、分别列中的枢轴记录也得到了最终在序列中的位置而被存放好，并且它们又分别分割出独立的两个子序列分割出独立的两个子序列。显然，这是一个递归的过程，不断进行下去，。显然，这是一个递归的过程，不断进行下去，直到每个待排序的子序列中只有一个记录时为止，整个排序过程结束。直到每个待排序的子序列中只有一个记录时为止，整个排序过程结束。 快速排序是对冒泡排序的一种改进。快速排序是对冒泡排序的一种改进。 如何把一个记录组分成两个部分？通常是以序列中第一个记录的关键字如何把一个记录组分成两个部分？通常是以序列中第一个记录的关键字值作为枢轴记录。值作为枢轴记录。排序过程：排序过程： 对对rstrst中记录进行一趟快

30、速排序，附设两个指针中记录进行一趟快速排序，附设两个指针i i和和j j，设枢轴记录设枢轴记录rp=rsrp=rs，x=rp.keyx=rp.key 初始时令初始时令i=s,j=ti=s,j=t 首先从首先从 j j 所指位置向前搜索第一个关键字所指位置向前搜索第一个关键字小于小于 x x 的记录，的记录，并和并和 rp rp 交换；交换； 再从再从 i i 所指位置起向后搜索，找到第一个关键字所指位置起向后搜索，找到第一个关键字大于大于 x x 的记录，和的记录，和 rp rp 交换；交换； 重复上述两步，直至重复上述两步，直至i=ji=j为止为止 再分别对两个子序列进行快速排序，直到每个子

31、序列再分别对两个子序列进行快速排序，直到每个子序列只含只含有一个记录有一个记录为止。为止。例例初始关键字：初始关键字： 49 38 65 97 76 13 27 50 ijxji 完成一趟排序：完成一趟排序： ( 27 38 13) 49 (76 97 65 50) 分别进行快速排序：分别进行快速排序： ( 13) 27 (38) 49 (50 65) 76 (97) 快速排序结束：快速排序结束： 13 27 38 49 50 65 76 974927ijijij4965ji1349ij4997ij算法：算法：int Partition(int i,int j) int Partition(i

32、nt i,int j) /i/i、j j为形参，分别代表为形参，分别代表lowlow和和highhigh RecType pivot=Ri; while(ij) while(ij) / / 从表的两端交替地向中间扫描从表的两端交替地向中间扫描 while(i=pivot.key) while(i=pivot.key) j- -; j- -; if (ij) Ri+=Rj; if (ij) Ri+=Rj; while (ij&Ri.key=pivot.key) while (ij&Ri.key=pivot.key) i+ +; i+ +; if (ij) if (ij) Rj- -=Ri; Rj

33、- -=Ri; Ri=pivot; return i; Ri=pivot; return i; void QuickSort(int low,int high) void QuickSort(int low,int high) / / 递归形式的快排序递归形式的快排序 int pivotpos,k;int pivotpos,k; if (lowhigh) if (lowhigh) pivotpos=Partition(low,high); pivotpos=Partition(low,high); /调用调用Partition(low,high)Partition(low,high)函数函数

34、QuickSort(low,pivotpos-1); QuickSort(low,pivotpos-1); / / 对低子表递归排序对低子表递归排序 QuickSort(pivotpos+1,high); QuickSort(pivotpos+1,high); / / 对高子表递归排序对高子表递归排序 算法评价算法评价时间复杂度时间复杂度 最好情况最好情况（每次总是选到中间值作枢轴）（每次总是选到中间值作枢轴）T(n)=O(nlogT(n)=O(nlog2 2n)n)经经验证明快速排序为同数量级下平均性能最好的。验证明快速排序为同数量级下平均性能最好的。 最坏情况最坏情况（每次总是选到最小或最

35、大元素作枢轴）（每次总是选到最小或最大元素作枢轴）-退化为冒退化为冒泡排序泡排序T(n)=O(n)T(n)=O(n)。空间复杂度：需栈空间以实现递归空间复杂度：需栈空间以实现递归最坏情况：最坏情况：S(n)=O(n)S(n)=O(n)一般情况：一般情况：S(n)=O(logS(n)=O(log2 2n)n)快速排序为不稳定排序。快速排序为不稳定排序。10.4 10.4 选择排序选择排序 1. 1.简单选择简单选择排序排序基本思想：基本思想： （1）初始状态：整个数组）初始状态：整个数组 r 划分成两个部分，即有序区划分成两个部分，即有序区（初始为空）和无序区。（初始为空）和无序区。 （2）基本

36、操作：从无序区中选择关键字值最小的记录，将）基本操作：从无序区中选择关键字值最小的记录，将其与无序区的第一个记录交换（实质是添加到有序区尾部）。其与无序区的第一个记录交换（实质是添加到有序区尾部）。 从初态（有序区为空）开始，重复步骤（从初态（有序区为空）开始，重复步骤（2 2），直到终态），直到终态（无序区为空）。（无序区为空）。 排序过程排序过程 首先通过首先通过 n-1 n-1 次关键字比较，从次关键字比较，从 n n 个记录中找出关个记录中找出关键字最小的记录，键字最小的记录，将它与第一个记录交换将它与第一个记录交换； 再通过再通过 n-2 n-2 次比较，从剩余的次比较，从剩余的 n

37、-1 n-1 个记录中找出关个记录中找出关键字次小的记录，键字次小的记录，将它与第二个记录交换将它与第二个记录交换； 重复上述操作，共进行重复上述操作，共进行 n-1n-1趟趟 排序后，排序结束。排序后，排序结束。例例初始：初始： 49 38 65 97 76 13 27 kjjjjjjkki=11349一趟：一趟： 13 38 65 97 76 49 27 i=2kkjjjjj2738二趟：二趟： 13 27 65 97 76 49 38 三趟：三趟： 13 27 38 97 76 49 65 四趟：四趟： 13 27 38 49 76 97 65 五趟：五趟： 13 27 38 49 65

38、 97 76 六趟：六趟： 13 27 38 49 65 76 97 排序结束：排序结束： 13 27 38 49 65 76 97算法：算法： void Selectsort() for (i=1;in;i+) k=i; for (j=i+1;j=n;j+) if (Rj.keyas； for (j=2*s；j=m；j=j*2) /沿关键码较大的子女结点向下筛选沿关键码较大的子女结点向下筛选 if (jaj.keyaj+1.key) j=j+1； / /为关键码较大的元素下标为关键码较大的元素下标 if (ac.keyaj.key) baeak； / ac/ ac应插入在位置应插入在位置s

39、s上上 h-as=h-aj； s=j； / / 使使s s结点满足堆定义结点满足堆定义 h-as=ac； / / 插入插入 void HeapSoat (S_TBL *h) for (i=h-length/2；i0；i- -) / / 将将a1.lengtha1.length建成堆建成堆 HeapAdjust (h，i，h-length)； for (i=h-length；i1；i- -) h-a1h-ai； / / 堆顶与堆低元素交换堆顶与堆低元素交换 HeapAdjust (h，1，i-1)； / / 将将a1.i-1a1.i-1重新调整为堆重新调整为堆 算法评价：算法评价：时间复杂度：最好、坏情况下时间复杂度：最好、坏情况下T(n)=O(nlogn)-n较大时比较有效较大时比较有效空间复杂度：空间复杂度：S(n)=O(1)堆排序为不稳定排序。堆排序为不稳定排序。10.5 10.5 归并排序归并排序 归并排序是将两个或两个以上的有序子表合并成一个新归并排序是将两个或两个以上的有序子表合并成一个新的有序表。的有序表。基本思想：基本思想： （1）将）将n个记录的待排序序列看成是有个记录的待排序序列看成是有n个长度都为个长度都为1的有的有序子表组成。序子表组成。 （2）将两两相邻的子表归并为一个有序子表。）将两两相邻的子