数据结构排序技术

《数据结构排序技术》由会员分享，可在线阅读，更多相关《数据结构排序技术（88页珍藏版）》请在装配图网上搜索。

1、数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社第八章第八章 排序技术排序技术本章的基本内容是：本章的基本内容是：排序的基本概念排序的基本概念插入排序插入排序交换排序交换排序选择排序选择排序数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社概概 述述 排序：排序：给定一组给定一组记录记录的集合的集合r1,r2,rn，其相应其相应的关键码分别为的关键码分别为k1,k2,kn，排序是将这些记录排序是将这些记录排列成顺序为排列成顺序为rs1,rs2,rsn的一个序列，使得相应的一个序列，使得相应的关键码满足的关键码满足ks 1ks 2ks n（称为升序）或称为升序）或ks1ks

2、2ksn（称为降序）。称为降序）。正序：正序：待排序序列中的记录已按关键码排好序。待排序序列中的记录已按关键码排好序。逆序（反序）：逆序（反序）：待排序序列中记录的排列顺序与排好待排序序列中记录的排列顺序与排好序的顺序正好相反。序的顺序正好相反。排序的基本概念排序的基本概念数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社排序算法的稳定性：排序算法的稳定性：假定在待排序的记录集中，存在假定在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的多个具有相同键值的记录，若经过排序，这些记录的相对次序相对次序仍然保持不变，即在原序列中，仍然保持不变，即在原序列中，ki=kj

3、且且ri在在rj之前，之前，而在排序后的序列中，而在排序后的序列中，ri仍在仍在rj之前，则称这种之前，则称这种排序算法是稳定的；否则称为不稳定的。排序算法是稳定的；否则称为不稳定的。概概 述述 排序的基本概念排序的基本概念学号学号姓名姓名高数高数英语英语思想品德思想品德0001王王 军军85880002李李 明明64920003汤晓影汤晓影8586687278数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社概概 述述 排序的基本概念排序的基本概念单键排序：单键排序：根据一个关键码进行的排序；根据一个关键码进行的排序；多键排序：多键排序：根据多个关键码进行的排序。根据多个关键码进行

4、的排序。学号学号姓名姓名高数高数英语英语思想品德思想品德0001王王 军军85880002李李 明明64920003汤晓影汤晓影8586687278按学号排序按学号排序单键排序单键排序按成绩（高数英语思想品德）排序按成绩（高数英语思想品德）排序多键排序多键排序数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社概概 述述 排序的基本概念排序的基本概念设关键码分别为设关键码分别为k1,k2,km，多键排序有两种方法：，多键排序有两种方法：依次对记录进行依次对记录进行m次排序，第一次按次排序，第一次按k1排序，第二排序，第二次按次按k2排序，依此类推。这种方法要求各趟排序所用排序，依此类推

5、。这种方法要求各趟排序所用的算法是稳定的；的算法是稳定的；将关键码将关键码k1,k2,km分别视为字符串依次首尾连接分别视为字符串依次首尾连接在一起，形成一个新的字符串，然后，对记录序列按在一起，形成一个新的字符串，然后，对记录序列按新形成的字符串排序。新形成的字符串排序。多键排序多键排序单键排序单键排序数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社排序的分类排序的分类1.内排序：内排序：在排序的整个过程中，待排序的所有记录在排序的整个过程中，待排序的所有记录全部被放置在内存中全部被放置在内存中2.外排序外排序：由于待排序的记录个数太多，不能同时放由于待排序的记录个数太多，不能同

6、时放置在内存，而需要将一部分记录放置在内存，另一部置在内存，而需要将一部分记录放置在内存，另一部分记录放置在外存上，整个排序过程需要在内外存之分记录放置在外存上，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。间多次交换数据才能得到排序的结果。概概 述述 排序的基本概念排序的基本概念数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社排序的分类排序的分类1.基于比较：基于比较：基本操作基本操作关键码的比较和记录的移动，关键码的比较和记录的移动，其最差时间下限已经被证明为其最差时间下限已经被证明为（nlog2n）。2.不基于比较不基于比较：根据关键码的分布特征。：根据关键码的

7、分布特征。概概 述述 排序的基本概念排序的基本概念基于比较的内排序基于比较的内排序1.插入排序插入排序2.交换排序交换排序3.选择排序选择排序4.归并排序归并排序数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社1.基本操作基本操作。内排序在排序过程中的基本操作：。内排序在排序过程中的基本操作：比较比较：关键码之间的比较；：关键码之间的比较；移动移动：记录从一个位置移动到另一个位置。：记录从一个位置移动到另一个位置。2.辅助存储空间辅助存储空间。辅助存储空间是指在数据规模一定的条件下，除了存辅助存储空间是指在数据规模一定的条件下，除了存放待排序记录占用的存储空间之外，执行算法所需要放

8、待排序记录占用的存储空间之外，执行算法所需要的其他存储空间。的其他存储空间。3.算法本身的复杂程度算法本身的复杂程度。排序算法的性能排序算法的性能概概 述述 数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社排序算法的存储结构排序算法的存储结构概概 述述 从操作角度看，排序是线性结构的一种操作，待排序从操作角度看，排序是线性结构的一种操作，待排序记录可以用记录可以用顺序顺序存储结构或存储结构或链接链接存储结构存储。存储结构存储。假定假定2：将待排序的记录序列排序为将待排序的记录序列排序为升序升序序列。序列。int rn+1;/待排序记录存储在待排序记录存储在r1rn，r0留做他用留做

9、他用假定假定1 1：采用采用顺序顺序存储结构，关键码为存储结构，关键码为整型整型，且记录，且记录只有关键码只有关键码一个一个数据项。数据项。数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社插入排序插入排序插入排序的主要操作是插入排序的主要操作是插入插入，其基本思想是：，其基本思想是：每次将一个待排序的记录按其关键码的大小插每次将一个待排序的记录按其关键码的大小插入到一个已经排好序的有序序列中，直到全部入到一个已经排好序的有序序列中，直到全部记录排好序为止。记录排好序为止。数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社基本思想基本思想：在插入第：在插入第 i（i1）个记

10、录时，前面的）个记录时，前面的 i-1个记录已经排好序。个记录已经排好序。直接插入排序直接插入排序插入排序插入排序有序序列有序序列无序序列无序序列12i-1ini+112i-1ini+1数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社基本思想基本思想：在插入第：在插入第 i（i1）个记录时，前面的）个记录时，前面的 i-1个记录已经排好序。个记录已经排好序。（1）如何构造初始的有序序列？）如何构造初始的有序序列？（2）如何查找待插入记录的插入位置）如何查找待插入记录的插入位置?直接插入排序直接插入排序插入排序插入排序需解决的关键问题需解决的关键问题?数据结构（数据结构（C+版）版）

11、清华大学出版社清华大学出版社r 0 1 2 3 4 5 6插入排序插入排序i=2i=3i=4i=6i=5r0的作用的作用?暂存单元暂存单元监视哨监视哨数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社解决方法：解决方法：将第将第1个记录看成是初始有序表，然后从第个记录看成是初始有序表，然后从第2个记录起个记录起依次插入到这个有序表中，直到将第依次插入到这个有序表中，直到将第n个记录插入。个记录插入。插入排序插入排序关键问题关键问题(1)如何构造初始的有序序列？如何构造初始的有序序列？算法描述：算法描述：for(i=2;i=n;i+)插入第插入第i个记录，即第个记录，即第i趟直接插入排

12、序；趟直接插入排序；数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社关键问题关键问题(2)如何查找待插入记录的插入位置如何查找待插入记录的插入位置?解决方法：解决方法：在在i-1个记录的有序区个记录的有序区r1 ri-1中插入记录中插入记录ri，首，首先顺序查找先顺序查找ri的正确插入位置，然后将的正确插入位置，然后将ri插入到相插入到相应位置。应位置。r0有两个作用：有两个作用：1.进入循环之前暂存了进入循环之前暂存了ri的值，使得不致于因记录的值，使得不致于因记录的后移而丢失的后移而丢失ri的内容；的内容；2.在查找插入位置的循环在查找插入位置的循环中充当中充当哨兵哨兵。插入排

13、序插入排序算法描述：算法描述：r0=ri;j=i-1;while(r0rj)rj+1=rj;j-;数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社void insertSort(int r,int n)for(i=2;i=n;i+)r0=ri;j=i-1;while(r0=ri-1，内层循，内层循环会出现什么情况环会出现什么情况?数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社直接插入排序算法性能分析直接插入排序算法性能分析最好情况下（正序）：最好情况下（正序）：插入排序插入排序时间复杂度为时间复杂度为O(n)。比较次数：比较次数：n-1移动次数：移动次数：2(n-1)

14、数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社直接插入排序算法性能分析直接插入排序算法性能分析插入排序插入排序最好最好情况下（正序）：情况下（正序）：比较次数：比较次数：n-1移动次数：移动次数：2(n-1)最坏最坏情况下（逆序或反序）：情况下（逆序或反序）：时间复杂度为时间复杂度为O(n2)。比较次数：比较次数：移动次数：移动次数：2)1)(2(2-+=nnini2)1)(4(1-+=+nnin2=i）（时间复杂度为时间复杂度为O(n)。数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社平均平均情况下（随机排列）：情况下（随机排列）：直接插入排序算法性能分析直接插入排

15、序算法性能分析插入排序插入排序时间复杂度为时间复杂度为O(n2)。比较次数：比较次数：移动次数：移动次数：4)1)(4(-+=nnn2=i4)1)(2(2-+=nnnii2（21+i）数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社空间性能：空间性能：需要一个记录的辅助空间。需要一个记录的辅助空间。直接插入排序算法是一种直接插入排序算法是一种稳定稳定的排序算法。的排序算法。直接插入排序算法性能分析直接插入排序算法性能分析插入排序插入排序直接插入排序算法简单、容易实现，适用于待排直接插入排序算法简单、容易实现，适用于待排序记录基本有序或待排序记录较小时。序记录基本有序或待排序记录较小

16、时。当待排序的记录个数较多时，大量的比较和移动当待排序的记录个数较多时，大量的比较和移动操作使直接插入排序算法的效率降低。操作使直接插入排序算法的效率降低。数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社插入排序插入排序如何改进直接插入排序如何改进直接插入排序?注意到，在插入第注意到，在插入第 i（i1）个记录时，前面的）个记录时，前面的 i-1 个个记录已经排好序，则在寻找插入位置时，可以用折记录已经排好序，则在寻找插入位置时，可以用折半查找来代替顺序查找，从而较少比较次数。半查找来代替顺序查找，从而较少比较次数。请同学们写出这个改进的直接插入排序算法，并分析请同学们写出这个改进

17、的直接插入排序算法，并分析时间性能。时间性能。数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社希尔排序希尔排序改进的着眼点：改进的着眼点：（1）若待排序记录按关键码）若待排序记录按关键码基本有序基本有序时，直接插入时，直接插入排序的效率可以大大提高；排序的效率可以大大提高；（2）由于直接插入排序算法简单，则在待排序记录）由于直接插入排序算法简单，则在待排序记录数量数量n较小较小时效率也很高。时效率也很高。插入排序插入排序数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社（1）应如何分割待排序记录，才能保证整个序列逐步）应如何分割待排序记录，才能保证整个序列逐步向基本有序发

18、展？向基本有序发展？（2）子序列内如何进行直接插入排序？）子序列内如何进行直接插入排序？插入排序插入排序需解决的关键问题需解决的关键问题?基本思想：基本思想：将整个待排序记录将整个待排序记录分割分割成若干个子序列，成若干个子序列，在子序列内分别进行直接插入排序，待整个序列中的在子序列内分别进行直接插入排序，待整个序列中的记录记录基本有序基本有序时，对全体记录进行直接插入排序。时，对全体记录进行直接插入排序。希尔排序希尔排序数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社基本有序基本有序：接近正序，例如：接近正序，例如1,2,8,4,5,6,7,3,9；局部有序局部有序：部分有序，例

19、如：部分有序，例如6,7,8,9,1,2,3,4,5。局部有序不能提高直接插入排序算法的时间性能。局部有序不能提高直接插入排序算法的时间性能。插入排序插入排序希尔排序希尔排序分割待排序记录的目的分割待排序记录的目的?1.减少待排序记录个数；减少待排序记录个数；2.使整个序列向基本有序发展。使整个序列向基本有序发展。子序列的构成不能是简单地子序列的构成不能是简单地“逐段分割逐段分割”，而是将相，而是将相距某个距某个“增量增量”的记录组成一个子序列。的记录组成一个子序列。启示启示?数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社希尔插入排序过程示例希尔插入排序过程示例 1 2 3 4

20、5 6 7 8 9初始序列初始序列插入排序插入排序d=4d=2d=1数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社解决方法：解决方法：将相隔某个将相隔某个“增量增量”的记录组成一个子序列。的记录组成一个子序列。增量应如何取？增量应如何取？希尔最早提出的方法是希尔最早提出的方法是d1=n/2，di+1=di/2。关键问题关键问题(1)(1)应如何分割待排序记录？应如何分割待排序记录？插入排序插入排序算法描述：算法描述：for(d=n/2;d=1;d=d/2)以以d为增量，进行组内直接插入排序；为增量，进行组内直接插入排序；数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社

21、解决方法：解决方法：在插入记录在插入记录ri时，自时，自ri-d起往前跳跃式（跳跃幅起往前跳跃式（跳跃幅度为度为d）搜索待插入位置，并且搜索待插入位置，并且r0只是暂存单元，只是暂存单元，不是哨兵。当搜索位置不是哨兵。当搜索位置0，表示插入位置已找到。，表示插入位置已找到。在搜索过程中，记录后移也是跳跃在搜索过程中，记录后移也是跳跃d个位置。个位置。在整个序列中，前在整个序列中，前d个记录分别是个记录分别是d个子序列中的个子序列中的第一个记录，所以从第第一个记录，所以从第d+1个记录开始进行插入。个记录开始进行插入。插入排序插入排序关键问题关键问题(2)子序列内如何进行直接插入排序？子序列内如

22、何进行直接插入排序？数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社算法描述：算法描述：for(i=d+1;i0&r0rj)rj+d=rj;/记录后移记录后移d个位置个位置 j=j-d;/比较同一子序列的前一个记录比较同一子序列的前一个记录 rj+d=r0;插入排序插入排序关键问题关键问题(2)子序列内如何进行直接插入排序？子序列内如何进行直接插入排序？数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社希尔排序算法的时间性能希尔排序算法的时间性能希尔排序算法的时间性能是所取希尔排序算法的时间性能是所取增量增量的函数，而到目的函数，而到目前为止尚未有人求得一种最好的增量序列

23、。前为止尚未有人求得一种最好的增量序列。研究表明，希尔排序的时间性能在研究表明，希尔排序的时间性能在O(n2)和和O(nlog2n)之间。当之间。当n在某个特定范围内，希尔排序所需的比较在某个特定范围内，希尔排序所需的比较次数和记录的移动次数约为次数和记录的移动次数约为O(n1.3)。插入排序插入排序希尔排序开始时增量较大，每个子序列中的记录个数希尔排序开始时增量较大，每个子序列中的记录个数较少，从而排序速度较快；当增量较小时，虽然每个较少，从而排序速度较快；当增量较小时，虽然每个子序列中记录个数较多，但整个序列已基本有序，排子序列中记录个数较多，但整个序列已基本有序，排序速度也较快。序速度也

24、较快。数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社课堂练习：1.欲将序列（欲将序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的关键码按）中的关键码按字母升序重排，则初始步长为字母升序重排，则初始步长为4的希尔排序一趟的结果是？的希尔排序一趟的结果是？答：答：原始序列：原始序列：Q,H,C,Y,P,A,M,S,R,D,F,X shellshell一趟后：一趟后：2.以关键字序列（以关键字序列（256，301，751，129，937，863，742，694，076，438）为例，分别写出执行以下算法的）为例，分别写出执行以下算法的各趟各趟排序结束时，关排序结束时，关键字序

25、列的状态，并说明这些排序方法中，哪些易于在链表（包键字序列的状态，并说明这些排序方法中，哪些易于在链表（包括各种单、双、循环链表）上实现？括各种单、双、循环链表）上实现？直接插入排序直接插入排序 希尔排序（取希尔排序（取dk=5,3,1）P,Q,R,A,D,H,C,F,M,S,X,Y答：答：显然，直接插入排序方法易于在链表上实现；但希尔排显然，直接插入排序方法易于在链表上实现；但希尔排序方法因为是按增量选择记录，不易于在链表上实现。序方法因为是按增量选择记录，不易于在链表上实现。数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社交换排序的主要操作是交换排序的主要操作是交换交换，其主要

26、思想是：，其主要思想是：在待排序列中选在待排序列中选两个两个记录，将它们的关键码相记录，将它们的关键码相比较，如果比较，如果反序反序（即排列顺序与排序后的次序（即排列顺序与排序后的次序正好相反），则正好相反），则交换交换它们的存储位置。它们的存储位置。交换排序交换排序反序则反序则 交换交换数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社起泡排序起泡排序基本思想：基本思想：两两比较两两比较相邻相邻记录的关键码，如果反记录的关键码，如果反序则交换，直到没有反序的记录为止。序则交换，直到没有反序的记录为止。rj rj+1 ri+1 rn-1 rn 无序区无序区 有序区有序区 1ji-1

27、已经位于最终位置已经位于最终位置反序则交换反序则交换交换排序交换排序数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社起泡排序过程示例起泡排序过程示例 交换排序交换排序数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社交换排序交换排序Flag=1;Flag=1;for(i=1;in&flag;i+)for(i=1;in&flag;i+)flag=0;flag=0;for(j=1;jn-i;j+)for(j=1;jrj+1)flag=1;ri if(rjrj+1)flag=1;ri-rj+1-rj+1 因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换

28、，就说明序列有序，因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较。数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社起泡排序的时间性能分析起泡排序的时间性能分析最好情况（正序）：最好情况（正序）：交换排序交换排序比较次数：比较次数：n-1移动次数：移动次数：0 时间复杂度为时间复杂度为O(n)。数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社最坏情况（反序）：最坏情况（反序）：起泡排序的时间性能分析起泡排序的时间性能分析最好情况（正序）：最好情况（正序）：交换排序交换排序比较次数：比较次数：n-1移动次数：移动次数：0 时间复杂度为时间

29、复杂度为O(n)；时间复杂度为时间复杂度为O(n2)。比较次数：比较次数：移动次数：移动次数：2)1(1-=nn(n-i)n-1i2)1(1-=n3n3(n-i)n-1i平均情况：平均情况：时间复杂度为时间复杂度为O(n2)。数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社快速排序的基本思想快速排序的基本思想首先选一个首先选一个轴值轴值（即比较的基准），通过一趟排序将（即比较的基准），通过一趟排序将待排序记录待排序记录分割分割成独立的两部分，前一部分记录的关成独立的两部分，前一部分记录的关键码均键码均小于或等于小于或等于轴值，后一部分记录的关键码均轴值，后一部分记录的关键码均大大于

30、或等于于或等于轴值，然后分别对这两部分重复上述方法，轴值，然后分别对这两部分重复上述方法，直到整个序列有序。直到整个序列有序。交换排序交换排序如何选择轴值？如何选择轴值？如何实现分割（称一次划分）？如何实现分割（称一次划分）？如何处理分割得到的两个待排序子序列？如何处理分割得到的两个待排序子序列？如何判别快速排序的结束？如何判别快速排序的结束？需解决的关键问题需解决的关键问题?数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社选择轴值的方法：选择轴值的方法：1.使用第一个记录的关键码；使用第一个记录的关键码；2.选取序列中间记录的关键码；选取序列中间记录的关键码；3.比较序列中第一个

31、记录、最后一个记录和中间比较序列中第一个记录、最后一个记录和中间记录的关键码，取关键码居中的作为轴值并调换记录的关键码，取关键码居中的作为轴值并调换到第一个记录的位置；到第一个记录的位置；4.随机选取轴值。随机选取轴值。交换排序交换排序关键问题：关键问题：如何选择轴值？如何选择轴值？选取不同轴值的后果：选取不同轴值的后果：决定两个子序列的长度，子序列的长度最好相等。决定两个子序列的长度，子序列的长度最好相等。数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社ji交换排序交换排序关键问题：关键问题：如何实现一次划分？如何实现一次划分？jjiiijijjj数据结构（数据结构（C+版）版）

32、清华大学出版社清华大学出版社解决方法：解决方法：设待划分的序列是设待划分的序列是rs rt，设参数设参数i，j分别指向子分别指向子序列左、右两端的下标序列左、右两端的下标s和和t，令令rs为轴值，为轴值，（1）j从后从后向前向前扫描，直到扫描，直到rjri，将将rj移动到移动到ri的位置，使关键码小（同轴值相比）的记录移动到前的位置，使关键码小（同轴值相比）的记录移动到前面去；面去；（2）i从前从前向后向后扫描，直到扫描，直到rirj，将将ri移动到移动到rj的位置，使关键码大（同轴值比较）的记录移动到后的位置，使关键码大（同轴值比较）的记录移动到后面去；面去；（3）重复上述过程，直到）重复上

33、述过程，直到i=j。交换排序交换排序关键问题：关键问题：如何实现一次划分？如何实现一次划分？数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社交换排序交换排序关键问题：关键问题：如何实现一次划分？如何实现一次划分？算法描述：算法描述：int Partition(int r,int first,int end)i=first;j=end;/初始化初始化 while(ij)while(ij&ri=rj)j-；/右侧扫描右侧扫描 if(ij)rirj;i+;/将较小记录交换到前面将较小记录交换到前面 while(ij&ri=rj)i+；/左侧扫描左侧扫描 if(ij)rjri;j-;/将较

34、大记录交换到后面将较大记录交换到后面 retutn i;/i为轴值记录的最终位置为轴值记录的最终位置数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社解决方法：解决方法：对分割得到的两个子序列递归地执行快速排序。对分割得到的两个子序列递归地执行快速排序。交换排序交换排序关键问题：如何处理分割得到的两个待排序子序列？关键问题：如何处理分割得到的两个待排序子序列？ijij数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社算法描述：算法描述：交换排序交换排序关键问题：如何处理分割得到的两个待排序子序列？关键问题：如何处理分割得到的两个待排序子序列？void QuickSort(i

35、nt r,int first,int end)pivotpos=Partition(r,first,end);/一次划分一次划分 QuickSort(r,first,pivotpos-1);/对前一个子序列进行快速排序对前一个子序列进行快速排序 QuickSort(r,pivotpos+1,end);/对后一个子序列进行快速排序对后一个子序列进行快速排序数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社解决方法：解决方法：若待排序列中只有一个记录，显然已有序，否则进若待排序列中只有一个记录，显然已有序，否则进行一次划分后，再分别对分割所得的两个子序列进行一次划分后，再分别对分割所得的

36、两个子序列进行快速排序（即递归处理）。行快速排序（即递归处理）。交换排序交换排序关键问题：关键问题：如何判别快速排序的结束？如何判别快速排序的结束？数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社void QuickSort(int r,int first,int end)/在序列在序列 firstend中递归地进行快速排序中递归地进行快速排序 if(first end)pivotpos=Partition(r,first,end);QuickSort(r,first,pivotpos-1);QuickSort(r,pivotpos+1,end);算法描述：算法描述：交换排序交换排

37、序关键问题：关键问题：如何判别快速排序的结束？如何判别快速排序的结束？数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社交换排序交换排序例：例：38,27,55,50,13,49,65的快速排序递归树如下：的快速排序递归树如下：38135055496527快速排序的递归执行过程可以用递归树描述。快速排序的递归执行过程可以用递归树描述。快速排序的时间性能分析快速排序的时间性能分析数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社快速排序的时间性能分析快速排序的时间性能分析交换排序交换排序快速排序的时间性能快速排序的时间性能快速排序递归的深度快速排序递归的深度每次划分轴值的选取

38、每次划分轴值的选取数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社最好情况：最好情况：每一次划分对一个记录定位后，该记录的左侧子表与每一次划分对一个记录定位后，该记录的左侧子表与右侧子表的长度相同，为右侧子表的长度相同，为O(nlog2n)。快速排序的时间性能分析快速排序的时间性能分析交换排序交换排序T(n)2T(n/2)n 2(2T(n/4)n/2)n4T(n/4)2n 4(2T(n/8)n/4)2n8T(n/8)3n nT(1)nlog2nO(nlog2n)数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社最坏情况：最坏情况：每次划分只得到一个比上一次划分少一个记录的

39、子序每次划分只得到一个比上一次划分少一个记录的子序列（另一个子序列为空），为列（另一个子序列为空），为 O(n2)。最好情况：最好情况：每一次划分对一个记录定位后，该记录的左侧子表与每一次划分对一个记录定位后，该记录的左侧子表与右侧子表的长度相同，为右侧子表的长度相同，为O(nlog2n)。快速排序的时间性能分析快速排序的时间性能分析交换排序交换排序平均情况：平均情况：为为O(nlog2n)。)()1(21211nOnninni=-=-=）（数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社选择排序的主要操作是选择排序的主要操作是选择选择，其主要思想是：，其主要思想是：每趟排序在当前

40、待排序序列中选出关键码每趟排序在当前待排序序列中选出关键码最小最小的记录，添加到有序序列中。的记录，添加到有序序列中。选择排序选择排序有序序列有序序列12i-1ink无序序列无序序列ni+112i-1ii交换交换最小记录最小记录数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社简单选择排序简单选择排序基本思想：基本思想：第第i 趟在趟在n-i+1（i=1,2,n-1）个记录中选个记录中选取关键码最小的记录作为有序序列中的第取关键码最小的记录作为有序序列中的第i个记录。个记录。选择排序选择排序需解决的关键问题需解决的关键问题?如何在待排序序列中选出关键码最小的记录？如何在待排序序列中选

41、出关键码最小的记录？如何确定待排序序列中关键码最小的记录在有如何确定待排序序列中关键码最小的记录在有序序列中的位置？序序列中的位置？数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社简单选择排序示例简单选择排序示例最小者最小者 08交换交换21,08最小者最小者 16交换交换25,16最小者最小者 21交换交换49,21选择排序选择排序数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社最小者最小者 25交换交换25,28最小者最小者 28不交换不交换选择排序选择排序简单选择排序示例简单选择排序示例无序区只有无序区只有一个记录一个记录数据结构（数据结构（C+版）版）清华大学出

42、版社清华大学出版社解决方法：解决方法：设置一个整型变量设置一个整型变量index，用于记录在一趟比较的过程用于记录在一趟比较的过程中关键码中关键码最小的记录位置。最小的记录位置。选择排序选择排序关键问题：关键问题：如何在无序区中选出关键码最小的记录？如何在无序区中选出关键码最小的记录？indexindex index数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社算法描述：算法描述：index=i;for(j=i+1;j=n;j+)if(rjrindex)index=j;解决方法：解决方法：设置一个整型变量设置一个整型变量index，用于记录在一趟比较的过程用于记录在一趟比较的过程

43、中关键码中关键码最小的记录位置。最小的记录位置。关键问题：关键问题：如何在无序区中选出关键码最小的记录？如何在无序区中选出关键码最小的记录？数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社解决方法：解决方法：第第i趟简单选择排序的待排序区间是趟简单选择排序的待排序区间是ri rn，则则ri是无序是无序区第一个记录，所以，将区第一个记录，所以，将index所记载的关键所记载的关键码最小的记录与码最小的记录与ri交换交换。选择排序选择排序关键问题：如何确定关键问题：如何确定最小记录的最终位置？最小记录的最终位置？算法描述：算法描述：if(index!=i)ririndex;数据结构（数

44、据结构（C+版）版）清华大学出版社清华大学出版社void selectSort(int r,int n)for(i=1;in;i+)index=i;for(j=i+1;j=n;j+)if (rjrindex)index=j;if(index!=i)ririndex;简单选择排序算法简单选择排序算法选择排序选择排序数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社简单选择排序算法的性能分析简单选择排序算法的性能分析移动次数：移动次数：最好情况（正序）：最好情况（正序）：0次次选择排序选择排序数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社最坏情况：最坏情况：3(n-1)次次

45、简单选择排序算法的性能分析简单选择排序算法的性能分析移动次数：移动次数：最好情况（正序）：最好情况（正序）：0次次选择排序选择排序空间性能：空间性能：需一个辅助空间。需一个辅助空间。稳定性：稳定性：是一种稳定的排序算法。是一种稳定的排序算法。比较次数：比较次数：)()1(21211nOnninni=-=-=）（简单选择排序的时间复杂度为简单选择排序的时间复杂度为O(n2)。数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社堆的定义堆的定义堆是具有下列性质的堆是具有下列性质的完全二叉树完全二叉树：每个结点的值都：每个结点的值都小于或等于其左右孩子结点的值（称为小于或等于其左右孩子结点的

46、值（称为小根堆小根堆），），或每个结点的值都大于或等于其左右孩子结点的值或每个结点的值都大于或等于其左右孩子结点的值（称为（称为大根堆大根堆）。）。选择排序选择排序182032364525385040281.小根堆的根结点是小根堆的根结点是所有结点的最小者。所有结点的最小者。2.较小结点靠近根结较小结点靠近根结点，但不绝对。点，但不绝对。数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社堆的定义堆的定义堆是具有下列性质的堆是具有下列性质的完全二叉树完全二叉树：每个结点的值都：每个结点的值都小于或等于其左右孩子结点的值（称为小于或等于其左右孩子结点的值（称为小根堆小根堆），），或每个结

47、点的值都大于或等于其左右孩子结点的值或每个结点的值都大于或等于其左右孩子结点的值（称为（称为大根堆大根堆）。）。选择排序选择排序503845402836322018281.大根堆的根结点是大根堆的根结点是所有结点的最大者。所有结点的最大者。2.较大结点靠近根结较大结点靠近根结点，但不绝对。点，但不绝对。数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社堆和序列的关系堆和序列的关系选择排序选择排序将堆用顺序存储结构来存储，则堆对应一组序列。将堆用顺序存储结构来存储，则堆对应一组序列。5038454028363220182850 38 45 32 36 40 28 20 18 281 2

48、 3 4 5 6 7 8 9 10采用顺序存储采用顺序存储数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社基本思想：基本思想：首先将待排序的记录序列构造成一个堆，首先将待排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大者，然后将它从堆此时，选出了堆中所有记录的最大者，然后将它从堆中移走，并将剩余的记录再调整成堆，这样又找出了中移走，并将剩余的记录再调整成堆，这样又找出了次小的记录，以此类推，直到堆中只有一个记录。次小的记录，以此类推，直到堆中只有一个记录。选择排序选择排序堆排序堆排序需解决的关键问题需解决的关键问题?如何由一个无序序列建成一个堆（即初始建堆）？如何由一个无

49、序序列建成一个堆（即初始建堆）？如何处理堆顶记录？如何处理堆顶记录？如何调整剩余记录，成为一个新堆（即重建堆）？如何调整剩余记录，成为一个新堆（即重建堆）？数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社堆调整堆调整堆调整：堆调整：在一棵完全二叉树中，根结点的左右子树均是在一棵完全二叉树中，根结点的左右子树均是堆，如何调整根结点，使整个完全二叉树成为一个堆？堆，如何调整根结点，使整个完全二叉树成为一个堆？选择排序选择排序283632161825321618253628数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社void sift(int r,int k,int m)

50、/要筛选结点的编号为要筛选结点的编号为k，堆中最后一个结点的编号为堆中最后一个结点的编号为m i=k;j=2*i;while(j=m)/筛选还没有进行到叶子筛选还没有进行到叶子 if(jm&rjrj)break;else ri rj;i=j;j=2*i;选择排序选择排序堆调整堆调整算法描述：算法描述：数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社选择排序选择排序关键问题：关键问题：如何由一个无序序列建成一个堆？如何由一个无序序列建成一个堆？282516321836163216282518362532162818362528323628161825数据结构（数据结构（C+版）版）清

51、华大学出版社清华大学出版社算法描述：算法描述：for(i=n/2;i=1;i-)sift(r,i,n);选择排序选择排序关键问题：关键问题：如何由一个无序序列建成一个堆？如何由一个无序序列建成一个堆？最后一个结点（叶子）的序号是最后一个结点（叶子）的序号是n，则最后一个分支结点即为结点则最后一个分支结点即为结点n的双亲，的双亲，其序号是其序号是n/2。数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社选择排序选择排序关键问题：关键问题：如何处理堆顶记录？如何处理堆顶记录？32362816182536 28 32 25 18 161 2 3 4 5 6对对应应交换交换16 28 32

52、25 18 361 2 3 4 5 6对对应应321628361825数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社算法描述：算法描述：r1rn-i+1;选择排序选择排序关键问题：关键问题：如何处理堆顶记录？如何处理堆顶记录？解决方法：解决方法：第第 i 次处理堆顶是将堆顶记录次处理堆顶是将堆顶记录r1与序列中第与序列中第n-i+1个个记录记录rn-i+1交换。交换。数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社321628361825选择排序选择排序关键问题：关键问题：如何调整剩余记录，成为一个新堆？如何调整剩余记录，成为一个新堆？1628163236182528

53、3236181625数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社解决方法：解决方法：第第 i 次调整剩余记录，此时，剩余记录有次调整剩余记录，此时，剩余记录有n-i个，调整个，调整根结点至第根结点至第n-i个记录。个记录。选择排序选择排序关键问题：关键问题：如何调整剩余记录，成为一个新堆？如何调整剩余记录，成为一个新堆？算法描述：算法描述：sift(r,1,n-i);数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社堆排序算法堆排序算法void HeapSort(int r,int n)for(i=n/2;i=1;i-)/初建堆初建堆 sift(r,i,n);for(

54、i=1;in;i+)r1rn-i+1;/移走堆顶移走堆顶 sift(r,1,n-i);/重建堆重建堆 选择排序选择排序数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社堆排序算法的性能分析堆排序算法的性能分析第第1个个for循环是初始建堆，需要循环是初始建堆，需要O(n)时间；时间；第第2个个for循环是输出堆顶重建堆，共需要取循环是输出堆顶重建堆，共需要取n-1次堆顶次堆顶记录，第记录，第 i 次取堆顶记录重建堆需要次取堆顶记录重建堆需要O(log2i)时间，需时间，需要要O(nlog2n)时间；时间；因此整个时间复杂度为因此整个时间复杂度为O(nlog2n)，这是堆排序的这是堆排

55、序的最好最好、最坏最坏和和平均平均的时间代价。的时间代价。选择排序选择排序数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社归并排序归并排序归并排序的主要操作是归并排序的主要操作是归并归并，其主要思想是：，其主要思想是：将若干有序序列逐步归并，最终得到一个有序将若干有序序列逐步归并，最终得到一个有序序列。序列。归并排序归并排序归并：归并：将两个或两个以上的有序序列合并成一个有序将两个或两个以上的有序序列合并成一个有序序列的过程。序列的过程。数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社基本思想：基本思想：将一个具有将一个具有n个待排序记录的序列看成个待排序记录的序列看成

56、是是n个长度为个长度为1的有序序列，然后进行两两归并，得的有序序列，然后进行两两归并，得到到n/2个长度为个长度为2的有序序列，再进行两两归并，得的有序序列，再进行两两归并，得到到n/4个长度为个长度为4的有序序列，的有序序列，直至得到一个，直至得到一个长度为长度为n的有序序列为止。的有序序列为止。二路归并排序二路归并排序归并排序归并排序需解决的关键问题需解决的关键问题?如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？怎样完成一趟归并？怎样完成一趟归并？如何控制二路归并的结束？如何控制二路归并的结束？数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社 60 2

57、0 31 5 44 55 65数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社void Merge(int r,int r1,int s,int m,int t)i=s;j=m+1;k=s;while(i=m&j=t)if(ri=rj)r1k+=ri+;else r1k+=rj+;if(i=m)while(i=m)/收尾处理收尾处理 r1k+=ri+;/前一个子序列前一个子序列 else while(j=t)r1k+=rj+;/后一个子序列后一个子序列 归并排序归并排序关键问题：关键问题：如何将两个有序序列合成一个有序序列？如何将两个有序序列合成一个有序序列？算法描述：算法描述：数

58、据结构（数据结构（C+版）版）清华大学出版社清华大学出版社void MergePass(int r,int r1,int n,int h)i=1;while(in-2h+1)/情况情况1 Merge(r,r1,i,i+h-1,i+2*h-1);i+=2*h;if(in-h+1)Merge(r,r1,i,i+h-1,n);/情况情况2 else for(k=i;k=n;k+)/情况情况3 r1k=rk;一趟归并排序算法一趟归并排序算法归并排序归并排序数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社算法描述：算法描述：void MergeSort(int r,int r1,int n)

59、h=1;while(hn)MergePass(r,r1,n,h);h=2*h;MergePass(r1,r,n,h);h=2*h;归并排序归并排序关键问题：关键问题：如何控制二路归并的结束？如何控制二路归并的结束？数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社二路归并排序算法的性能分析二路归并排序算法的性能分析归并排序归并排序时间性能：时间性能：一趟归并操作是将一趟归并操作是将r1rn中相邻的长度为中相邻的长度为h的有序的有序序列进行两两归并，并把结果存放到序列进行两两归并，并把结果存放到r11r1n中，中，这需要这需要O(n)时间。整个归并排序需要进行时间。整个归并排序需要进行

60、 趟，趟，因此，总的时间代价是因此，总的时间代价是O(nlog2n)。这是归并排序算这是归并排序算法的法的最好最好、最坏最坏、平均平均的时间性能。的时间性能。空间性能：空间性能：算法在执行时，需要占用与原始记录序列同样数量算法在执行时，需要占用与原始记录序列同样数量的存储空间，因此空间复杂度为的存储空间，因此空间复杂度为O(n)。n2log数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社各种排序方法的比较各种排序方法的比较对排序算法应该从以下几个方面综合考虑：对排序算法应该从以下几个方面综合考虑：时间复杂性；时间复杂性；空间复杂性；空间复杂性；稳定性；稳定性；算法简单性；算法简单性

61、；待排序记录个数待排序记录个数n的大小；的大小；记录本身信息量的大小；记录本身信息量的大小；关键码的分布情况。关键码的分布情况。数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社时间复杂度比较时间复杂度比较各种排序方法的比较各种排序方法的比较排序方法排序方法平均情平均情况况最好情最好情况况最坏情最坏情况况直接插入排直接插入排序序O(n2)O(n)O(n2)希 尔 排 序希 尔 排 序O(nlog2n)O(n1.3)O(n2)起 泡 排 序起 泡 排 序O(n2)O(n)O(n2)快 速 排 序快 速 排 序O(nlog2n)O(nlog2n)O(n2)简单选择排简单选择排序序O(n2

62、)O(n2)O(n2)数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社空间复杂度比较空间复杂度比较各种排序方法的比较各种排序方法的比较排序方法排序方法辅助空间辅助空间直接插入排序直接插入排序O(1)希 尔 排 序希 尔 排 序O(1)起 泡 排 序起 泡 排 序O(1)快 速 排 序快 速 排 序 O(log2n)O(n)简单选择排序简单选择排序O(1)堆排序堆排序O(1)归 并 排 序归 并 排 序O(n)数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社稳定性比较稳定性比较所有排序方法可分为两类，所有排序方法可分为两类，（1）一类是稳定的，包括直接插入排序、起泡排序、

63、）一类是稳定的，包括直接插入排序、起泡排序、直接选择排序和归并排序；直接选择排序和归并排序；（2）另一类是不稳定的，包括希尔排序、快速排序）另一类是不稳定的，包括希尔排序、快速排序和堆排序。和堆排序。各种排序方法的比较各种排序方法的比较数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社算法简单性比较算法简单性比较从算法简单性看，从算法简单性看，（1）一类是简单算法，包括直接插入排序、直接选）一类是简单算法，包括直接插入排序、直接选择排序和起泡排序，择排序和起泡排序，（2）另一类是改进后的算法，包括希尔排序、堆排）另一类是改进后的算法，包括希尔排序、堆排序、快速排序和归并排序，这些算法

64、都很复杂。序、快速排序和归并排序，这些算法都很复杂。各种排序方法的比较各种排序方法的比较数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社待排序的记录个数比较待排序的记录个数比较从待排序的记录个数从待排序的记录个数n的大小看，的大小看，n越小，采用简单越小，采用简单排序方法越合适，排序方法越合适，n越大，采用改进的排序方法越越大，采用改进的排序方法越合适。因为合适。因为n越小，越小，O(n2)同同O(nlog2n)的差距越小，的差距越小，并且输入和调试简单算法比输入和调试改进算法要并且输入和调试简单算法比输入和调试改进算法要少用许多时间。少用许多时间。各种排序方法的比较各种排序方法的

65、比较数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社记录本身信息量比较记录本身信息量比较记录本身信息量越大，移动记录所花费的时间就越多，记录本身信息量越大，移动记录所花费的时间就越多，所以对记录的移动次数较多的算法不利。所以对记录的移动次数较多的算法不利。排序方法排序方法最好情况最好情况最坏情况最坏情况平均情况平均情况直接插入排序直接插入排序O(n)O(n2)O(n2)起泡排序起泡排序0O(n2)O(n2)直接选择排序直接选择排序0O(n)O(n)各种排序方法的比较各种排序方法的比较数据结构（数据结构（C+版）版）清华大学出版社清华大学出版社关键码的分布情况比较关键码的分布情况比较当待排序记录按关键码有序时，插入排序和起泡排当待排序记录按关键码有序时，插入排序和起泡排序能达到序能达到O(n)的时间复杂度；对于快速排序而言，的时间复杂度；对于快速排序而言，这是最坏的情况，此时的时间性能蜕化为这是最坏的情况，此时的时间性能蜕化为O(n2)；选；选择排序、堆排序和归并排序的时间性能不随记录序择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。列中关键字的分布而改变。各种排序方法的比较各种排序方法的比较