数据结构第二十讲幻灯片.ppt

《数据结构第二十讲幻灯片.ppt》由会员分享，可在线阅读，更多相关《数据结构第二十讲幻灯片.ppt（46页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、数据结构第二十讲1第1页，共46页，编辑于2022年，星期六19.19.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,A,并已知并已知A A的左孩子的平衡因子为的左孩子的平衡因子为0 0右孩子的平衡因子为右孩子的平衡因子为1,1,则应作则应作()()型调型调整以使其平衡。整以使其平衡。A.A.LL B.LR C.RL D.RRLL B.LR C.RL D.RR27.27.设有一组记录的关键字为设有一组记录的关键字为1919，1414，2323，1 1，6868，2020，8484，2727，5555，1111，1

2、010，7979，用链地址法构造散列表，散列函数为，用链地址法构造散列表，散列函数为H H（keykey）=key=key MOD 13,MOD 13,散列地址为散列地址为1 1的链中有（的链中有（）个记录。）个记录。A A1 B.2 C.3 D.41 B.2 C.3 D.431.31.设哈希表长为设哈希表长为1414，哈希函数是，哈希函数是H(key)=key%11,H(key)=key%11,表中已有数据的关键字为表中已有数据的关键字为1515，3838，6161，8484共四个，现要将关键字为共四个，现要将关键字为4949的结点加到表中，用二次探测再的结点加到表中，用二次探测再散列法解决

3、冲突，则放入的位置是散列法解决冲突，则放入的位置是()()A A8 B8 B3 C3 C5 D5 D9 9 32.32.假定有假定有k k个关键字互为同义词，若用线性探测法把这个关键字互为同义词，若用线性探测法把这k k个关键字存入散列表个关键字存入散列表中，至少要进行多少次探测？中，至少要进行多少次探测？()()A Ak-1k-1次次 B.k B.k次次 C.k+1 C.k+1次次 D.k D.k（k+1k+1）/2/2次次C CD DD DD D第2页，共46页，编辑于2022年，星期六34.34.散列函数有一个共同的性质，即函数值应当以散列函数有一个共同的性质，即函数值应当以()()取其

4、值域的每个值。取其值域的每个值。A.A.最大概率最大概率 B.B.最小概率最小概率 C.C.平均概率平均概率 D.D.同等概率同等概率35.35.散列表的地址区间为散列表的地址区间为0-17,0-17,散列函数为散列函数为H(K)=K mod 17H(K)=K mod 17。采用线性探。采用线性探测法处理冲突，并将关键字序列测法处理冲突，并将关键字序列2626，2525，7272，3838，8 8，1818，5959依次存依次存储到散列表中。储到散列表中。（）元素）元素5959存放在散列表中的存放在散列表中的A A 8 B.9 C.10 D.11 8 B.9 C.10 D.11 （2 2）存放

5、元素）存放元素5959需要搜索的次数是（需要搜索的次数是（）。）。A A 2 B.3 C.4 D.5 2 B.3 C.4 D.536.36.将将1010个元素散列到个元素散列到100000100000个单元的哈希表中，则（个单元的哈希表中，则（）产生冲突。）产生冲突。A.A.一定会一定会 B.B.一定不会一定不会 C.C.仍可能会仍可能会D DD DC CC C第3页，共46页，编辑于2022年，星期六第第1010章章 排序排序 排序的概念及种类排序的概念及种类 插入法排序的各种具体实现方法及算法分析插入法排序的各种具体实现方法及算法分析 选择法排序的各种具体方法的实现及时间性能分析选择法排序

6、的各种具体方法的实现及时间性能分析 交换法排序的具体实现及性能分析交换法排序的具体实现及性能分析 归并排序和基数排序的各自实现算法归并排序和基数排序的各自实现算法第4页，共46页，编辑于2022年，星期六本章导读本章导读 排序是日常工作和软件设计中常用的运算之一。为排序是日常工作和软件设计中常用的运算之一。为了提高查询速度需要将无序序列按照一定的顺序组织了提高查询速度需要将无序序列按照一定的顺序组织成有序序列。由于需要排序的数据表的基本特性可能成有序序列。由于需要排序的数据表的基本特性可能存在差异，使得排序方法也不同。如何合理地组织数存在差异，使得排序方法也不同。如何合理地组织数据的逻辑顺序，

7、按照何种方式排出的序列最有效？这据的逻辑顺序，按照何种方式排出的序列最有效？这是本章要讨论的主题。本章主要介绍排序的概念及几是本章要讨论的主题。本章主要介绍排序的概念及几种最常见的排序方法，讨论其性能和特点，并在此基种最常见的排序方法，讨论其性能和特点，并在此基础上进一步讨论各种方法的适用场合，以便在实际应础上进一步讨论各种方法的适用场合，以便在实际应用中能根据具体的问题选择合适的排序方法。用中能根据具体的问题选择合适的排序方法。第5页，共46页，编辑于2022年，星期六10.1 10.1 10.1 10.1 排序的基本概念排序的基本概念排序的基本概念排序的基本概念10.1.1 10.1.1

8、10.1.1 10.1.1 排序及其分类排序及其分类排序及其分类排序及其分类1 1 1 1排序概念排序概念排序概念排序概念 排序（排序（sortingsorting）又称分类，是数据处理领域中一种很）又称分类，是数据处理领域中一种很常用的运算。排序就是把一组记录或数据元素的无序序列按常用的运算。排序就是把一组记录或数据元素的无序序列按照某个关键字值（关键字）递增或递减的次序重新排列的过照某个关键字值（关键字）递增或递减的次序重新排列的过程。程。排序的主要目的就是实现快速查找。日常生活中通过排序排序的主要目的就是实现快速查找。日常生活中通过排序以后进行检索的例子屡见不鲜。如电话簿、病历、档案室以

9、后进行检索的例子屡见不鲜。如电话簿、病历、档案室中的档案、图书馆和各种词典的目录表等，几乎都需要对中的档案、图书馆和各种词典的目录表等，几乎都需要对有序数据进行操作。有序数据进行操作。第6页，共46页，编辑于2022年，星期六假设含有假设含有n n个记录的序列为：个记录的序列为：RR1 1，R R2 2，R Rn n (1)(1)其相应的关键字序列为：其相应的关键字序列为：KK1 1，K K2 2 ，K Kn n 需确定需确定1 1，2 2，n n的一种排序的一种排序p p1 1，p p2 2，p pn n，使其，使其相应的关键字满足如下关系：相应的关键字满足如下关系：K Kp1p1KKp2p

10、2KKpn pn (2)(2)即使得式（即使得式（1 1）的序列成为一个按关键字有序的序列）的序列成为一个按关键字有序的序列RR p1 p1，R R p2 p2，R Rpnpn (3)(3)这这个个将将原原有有表表中中任任意意顺顺序序的的记记录录变变成成一一个个按按关关键键字字有有序序排排列列的的过程称为排序。过程称为排序。第7页，共46页，编辑于2022年，星期六2 2 2 2排序分类排序分类排序分类排序分类 (1)(1)增增排排序序和和减减排排序序：如如果果排排序序的的结结果果是是按按关关键键字字从从小小到到大的次序排列的，就是增排序，否则就是减排序。大的次序排列的，就是增排序，否则就是减

11、排序。（2）稳稳定定排排序序和和不不稳稳定定排排序序：假假设设Ki=KjKi=Kj（1in1in，1jn1jn，ijij），且且在在排排序序前前的的序序列列中中RiRi领领先先于于RjRj（即即ijij）。若若在在排排序序后后的的排排序序中中RiRi仍仍领领先先于于RjRj，即即那那些些具具有有相相同同关关键键字字的的记记录录，经经过过排排序序后后它它们们的的相相对对次次序序仍仍然然保保持持不不变变，则则称称这这种种排排序序方方法法是是稳稳定定的的；反反之之，若若RjRj领领先先于于RiRi，则称所用的方法是不稳定的。，则称所用的方法是不稳定的。第8页，共46页，编辑于2022年，星期六(3)

12、(3)内部排序与外部排序：在排序中，若数据表中的所有记录的内部排序与外部排序：在排序中，若数据表中的所有记录的排列过程都是在内存中进行的，称为内部排序。由于待排序的记排列过程都是在内存中进行的，称为内部排序。由于待排序的记录数量太多，在排序过程中不能同时把全部记录放在内存，需要录数量太多，在排序过程中不能同时把全部记录放在内存，需要不断地通过在内存和外存之间交换数据元素来完成整个排序的过不断地通过在内存和外存之间交换数据元素来完成整个排序的过程，称为外部排序。在外部排序情况下，只有部分记录进入内存，程，称为外部排序。在外部排序情况下，只有部分记录进入内存，在内存中进行内部排序，待排序完成后再交

13、换到外部存储器中加在内存中进行内部排序，待排序完成后再交换到外部存储器中加以保存。然后再将其它待排序的记录调入内存继续排序。这一过以保存。然后再将其它待排序的记录调入内存继续排序。这一过程需要反复进行，直到全部记录排出次序为止。显然，内部排序程需要反复进行，直到全部记录排出次序为止。显然，内部排序是外部排序的基础，本章主要介绍内部排序的各种方法。是外部排序的基础，本章主要介绍内部排序的各种方法。第9页，共46页，编辑于2022年，星期六10.1.2 10.1.2 10.1.2 10.1.2 排序算法的效率分析排序算法的效率分析排序算法的效率分析排序算法的效率分析 与许多算法一样，对各种排序算法

14、性能的评价主要从两个与许多算法一样，对各种排序算法性能的评价主要从两个方面来考虑，一是时间性能；二是空间性能。方面来考虑，一是时间性能；二是空间性能。1 1 时间复杂度分析时间复杂度分析时间复杂度分析时间复杂度分析 排排序序算算法法的的时时间间复复杂杂度度可可用用排排序序过过程程中中记记录录之之间间关关键键字字的的比较次数与记录的移动次数来衡量。比较次数与记录的移动次数来衡量。在在本本章章各各节节中中讨讨论论算算法法的的时时间间复复杂杂度度时时，一一般般都都按按平平均均时时间间复复杂杂度度进进行行估估算算；对对于于那那些些受受数数据据表表中中记记录录的的初初始始排排列列及及记记录录数数目目影影

15、响响较较大大的的算算法法，按最好情况和最坏情况分别进行估算。按最好情况和最坏情况分别进行估算。第10页，共46页，编辑于2022年，星期六2 2 2 2空间复杂度分析空间复杂度分析空间复杂度分析空间复杂度分析 排排序序算算法法的的空空间间复复杂杂度度是是指指算算法法在在执执行行时时所所需需的的附附加加存存储储空空间，也就是用来临时存储数据的内存使用情况。间，也就是用来临时存储数据的内存使用情况。在在以以后后的的排排序序算算法法中中，若若无无特特别别说说明明，均均假假定定待待排排序序的的记记录录序序列列采采用用顺顺序序表表结结构构来来存存储储，即即数数组组存存储储方方式式，并并假假定定是是按按关

16、关键键字字递递增增方方式式排排序序。为为简简单单起起见见，假假设设关关键键字字类类型型为为整整型型。待待排排序序的的顺顺序序表表类型的类型定义如下：类型的类型定义如下：typedef int KeyType /typedef int KeyType /定义关键字类型定义关键字类型 typedef struct dataType /typedef struct dataType /记录类型记录类型 keytype key;/keytype key;/关键字项关键字项 elemtype otherelement;/elemtype otherelement;/其他数据项其他数据项 RecType;

17、RecType;第11页，共46页，编辑于2022年，星期六10.2 10.2 10.2 10.2 插入排序插入排序插入排序插入排序 插入排序的基本思想是：每次将一个待排序的记录，按其关键字插入排序的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子表中的适当位置，直到全部记录插入大小插入到前面已经排好序的子表中的适当位置，直到全部记录插入完成为止。也就是说，将待序列表分成左右两部分，左边为有序表完成为止。也就是说，将待序列表分成左右两部分，左边为有序表（有序序列），右边为无序表（无序序列）。整个排序过程就是将右（有序序列），右边为无序表（无序序列）。整个排序过程就是将

18、右边无序表中的记录逐个插入到左边的有序表中，构成新的有序序列。边无序表中的记录逐个插入到左边的有序表中，构成新的有序序列。根据不同的插入方法，插入排序算法主要包括：直接插入排序、根据不同的插入方法，插入排序算法主要包括：直接插入排序、折半插入排序、表插入排序和希尔排序等。本章重点介绍直接插入折半插入排序、表插入排序和希尔排序等。本章重点介绍直接插入排序、折半插入排序和希尔排序。排序、折半插入排序和希尔排序。第12页，共46页，编辑于2022年，星期六10.2.1 10.2.1 10.2.1 10.2.1 直接插入排序直接插入排序直接插入排序直接插入排序 直直接接插插入入排排序序(Inserti

19、on(Insertion Sort)Sort)是是所所有有排排序序方方法法中中最最简简单单的的一一种种 排排 序序 方方 法法。其其 基基 本本 原原 理理 是是 顺顺 次次 地地 从从 无无 序序 表表 中中 取取 出出 记记 录录R Ri i(1in)(1in)，与与有有序序表表中中记记录录的的关关键键字字逐逐个个进进行行比比较较，找找出出其其应应该该插插入入的的位位置置，再再将将此此位位置置及及其其之之后后的的所所有有记记录录依依次次向向后后顺顺移移一一个个位置，将记录位置，将记录R Ri i插入其中。插入其中。假设待排序的假设待排序的n n个记录为个记录为RR1 1，R R2 2，R

20、Rn n，初始有序表为，初始有序表为RR1 1，初始无序表为，初始无序表为RR2 2 RRn n。当插入第。当插入第i i个记录个记录R Ri i(2in)(2in)时，时，有序表为有序表为RR1 1RRi-1i-1，无序表为，无序表为RRi i RRn n。将关键字。将关键字K K i i依次与依次与K Ki-1i-1，K Ki-2i-2 ，K K1 1进行比较，找出其应该插入的位置，将该位置及其以进行比较，找出其应该插入的位置，将该位置及其以后的记录向后顺移，插入记录后的记录向后顺移，插入记录R Ri i，完成序列中第，完成序列中第i i个记录的插入排个记录的插入排序。当完成序列中第序。当

21、完成序列中第n n个记录个记录R Rn n的插入后，整个序列排序完毕。的插入后，整个序列排序完毕。第13页，共46页，编辑于2022年，星期六向有序表中插入记录，主要完成如下操作：向有序表中插入记录，主要完成如下操作：(1)(1)搜索插入位置。搜索插入位置。(2)(2)移动插入点及其以后的记录空出插入位置。移动插入点及其以后的记录空出插入位置。(3)(3)插入记录。插入记录。假设将假设将n n个待排序的记录顺序存放在长度为个待排序的记录顺序存放在长度为n+1n+1的数组的数组R1R1Rn Rn 中。中。R0R0作为辅助空间，用来暂时存储需要插入的记录，作为辅助空间，用来暂时存储需要插入的记录，

22、起起监视哨监视哨的作用。直接插入排序算法如下的作用。直接插入排序算法如下:第14页，共46页，编辑于2022年，星期六void Insert_Sort(int R,int n)void Insert_Sort(int R,int n)int i,j;int i,j;for(i=2;i=n;i+)/for(i=2;i=n;i+)/表示待插入元素的下标表示待插入元素的下标 R0=Ri;/R0=Ri;/设置监视哨保存待插入元素，腾出设置监视哨保存待插入元素，腾出RiRi空间空间 j=i-1;/j j=i-1;/j指示当前空位置的前一个元素指示当前空位置的前一个元素 while(R0.keyRj.ke

23、y)/while(R0.keyRj.key)/搜索插入位置并后移腾出空搜索插入位置并后移腾出空 Rj+1=Rj;Rj+1=Rj;j-;j-;Rj+1=R0;/Rj+1=R0;/插入元素插入元素 第15页，共46页，编辑于2022年，星期六 显然，开始时有序表中只有显然，开始时有序表中只有1 1个记录个记录R1R1，然后需要将，然后需要将R2R2RnRn的的记录依次插入到有序表中，总共要进行记录依次插入到有序表中，总共要进行n-1n-1次插入操作。首先从无序表中次插入操作。首先从无序表中取出待插入的第取出待插入的第i i个记录个记录RiRi，暂存在，暂存在R0R0中；然后将中；然后将R0.key

24、R0.key依次与依次与Ri-1.keyRi-1.key，Ri-2.keyRi-2.key，进行比较，如果进行比较，如果R0.keyRi-R0.keyRi-j.keyj.key（1ji-11ji-1），则将），则将Ri-jRi-j后移一个单元；如果后移一个单元；如果R0.keyRi-j.keyR0.keyRi-j.key，则找到，则找到R0R0插入的位置插入的位置i-j+1i-j+1，此位置已经空，此位置已经空出，将出，将R0(R0(即即Ri)Ri)记录直接插入即可。然后采用同样的方法完成下记录直接插入即可。然后采用同样的方法完成下一个记录一个记录Ri+1Ri+1的插入排序。如此不断进行，直到

25、完成记录的插入排序。如此不断进行，直到完成记录RnRn的插的插入排序，整个序列变成按关键字非递减的有序序列为止。在搜索插入入排序，整个序列变成按关键字非递减的有序序列为止。在搜索插入位置的过程中，位置的过程中，R0.keyR0.key与与Ri-j.keyRi-j.key进行比较时，如果进行比较时，如果j=ij=i，则循环，则循环条件条件 R0.keyRi-j.key R0.keyRi-j.key不成立，从而退出不成立，从而退出while while 循环。由此可见循环。由此可见R0R0起到了监视哨的作用，避免了数组下标的出界。起到了监视哨的作用，避免了数组下标的出界。第16页，共46页，编辑于

26、2022年，星期六【例例10-1】假假设设有有7个个待待排排序序的的记记录录，它它们们的的关关键键字字分分别别为为23，4，15，8，19，24，15，用直接插入法进行排序。，用直接插入法进行排序。【解】直接插入排序过程如图【解】直接插入排序过程如图10-1所示。方括号所示。方括号 中为已排好中为已排好序的记录的关键字，有两个记录的关键字都为序的记录的关键字，有两个记录的关键字都为15，为表示区别，为表示区别，将后一个将后一个15加下划线。加下划线。第17页，共46页，编辑于2022年，星期六第18页，共46页，编辑于2022年，星期六空空间间性性能能：该该算算法法仅仅需需要要一一个个记记录录

27、的的辅辅助助存存储储空空间间，空空间间复复杂杂度度为为O(1)O(1)。稳定性稳定性：由于该算法在搜索插入位置时遇到关键字值相等的记录时就：由于该算法在搜索插入位置时遇到关键字值相等的记录时就停止操作，不会把关键字值相等的两个数据交换位置，所以该算法是稳停止操作，不会把关键字值相等的两个数据交换位置，所以该算法是稳定的。定的。时间性能时间性能：整个算法执行：整个算法执行for循环循环n-1次，每次循环中的基本操作次，每次循环中的基本操作是比较和移动，其总次数取决于数据表的初始特性，可能有以下是比较和移动，其总次数取决于数据表的初始特性，可能有以下几种情况：几种情况：（1）当初始记录序列的关键字

28、已是递增排列时，这是最好的情况。算）当初始记录序列的关键字已是递增排列时，这是最好的情况。算法中法中while语句的循环体执行次数为语句的循环体执行次数为0，因此，在一趟排序中关键字的比，因此，在一趟排序中关键字的比较次数为较次数为1，即，即R0的关键字与的关键字与Rj的关键字比较。而移动次数为的关键字比较。而移动次数为2，即，即Ri移动到移动到R0中，中，R0移动到移动到Rj+1中。所以，整个排序过程中的比中。所以，整个排序过程中的比较次数和移动次数分别为较次数和移动次数分别为(n-1)和和2(n-1)，因而其时间复杂度为因而其时间复杂度为O(n)。第19页，共46页，编辑于2022年，星期

29、六（2 2）当当初初始始数数据据序序列列的的关关键键字字序序列列是是递递减减排排列列时时，这这是是最最坏坏的的情情况况。在在第第i i次次排排序序时时，whilewhile语语句句内内的的循循环环体体执执行行次次数数为为i i。因因此此，关关键键字字的的比比较较次次数数为为i i，而而移移动动次次数数为为i+1i+1。所所以以，整整个个排排序序过过程程中中的的比比较较次次数数和和移移动动次次数数分别为：分别为：（3 3）一一般般情情况况下下，可可认认为为出出现现各各种种排排列列的的概概率率相相同同，因因此此取取上上述述两两种种情情况况的的平平均均值值，作作为为直直接接插插入入排排序序关关键键字

30、字的的比比较较次次数数和和记记录录移移动动次次数数，约为约为n n2 2/4/4。所以其时间复杂度为。所以其时间复杂度为O(nO(n2 2)。根据上述分析得知：当原始序列越接近有序时，该算法的执行效根据上述分析得知：当原始序列越接近有序时，该算法的执行效率就越高。率就越高。第20页，共46页，编辑于2022年，星期六10.2.2 10.2.2 10.2.2 10.2.2 折半插入排序折半插入排序折半插入排序折半插入排序 直直接接插插入入排排序序的的基基本本操操作作是是在在有有序序表表中中进进行行查查找找和和插插入入，而而在在有有序序表表中中查查找找插插入入位位置置，可可以以通通过过折折半半查查

31、找找的的方方法法实实现现，由由此此进进行行的插入排序称之为折半插入排序。的插入排序称之为折半插入排序。所谓折半查找，就是在插入所谓折半查找，就是在插入R Ri i时（此时时（此时R R1 1，R R2 2，R Ri-1i-1已排序）已排序），取，取R R i/2i/2 的关键字的关键字K K i/2i/2 与与K Ki i进行比较（进行比较（i/2i/2 表示取不大于表示取不大于i/2i/2的最大整数），如果的最大整数），如果K Ki iKK i/2i/2，R Ri i的插入位置只能在的插入位置只能在R R1 1和和R R i/2i/2 之间，则在之间，则在R R1 1和和R R i/2i/2

32、-1-1之间继续进行折半查找，否之间继续进行折半查找，否则在则在R R i/2i/2+1+1和和R Ri-1i-1 之间进行折半查找。如此反复直到最后确之间进行折半查找。如此反复直到最后确定插入位置为止。折半查找的过程是以处于有序表中间位置定插入位置为止。折半查找的过程是以处于有序表中间位置记录的关键字和记录的关键字和K Ki i比较，经过一次比较，便可排除一半记录，比较，经过一次比较，便可排除一半记录，把可插入的区间缩小一半，故称为折半。把可插入的区间缩小一半，故称为折半。第21页，共46页，编辑于2022年，星期六 设置始指针设置始指针lowlow，指向有序表的第一个记录，尾指针，指向有序

33、表的第一个记录，尾指针highhigh，指，指向有序表的最后一个记录，中间指针向有序表的最后一个记录，中间指针midmid指向有序表中间位置的指向有序表中间位置的记录。每次将待插入记录的关键字与记录。每次将待插入记录的关键字与midmid位置记录的关键字进行位置记录的关键字进行比较，从而确定待插入记录的插入位置。折半插入排序算法如下：比较，从而确定待插入记录的插入位置。折半插入排序算法如下：typedef int keytype;typedef int keytype;void Insert_halfSort(RecType R,int n)void Insert_halfSort(RecTy

34、pe R,int n)/*/*对顺序表对顺序表R R作折半插入排序作折半插入排序*/*/int i,j,low,high,mid;int i,j,low,high,mid;for(i=2;i=n;i+)for(i=2;i=n;i+)R0=Ri;/R0=Ri;/保存待插入元素保存待插入元素 low=1;high=i-1;/low=1;high=i-1;/设置初始区间设置初始区间 第22页，共46页，编辑于2022年，星期六while(low=high)/while(lowRmid.key)if(R0.keyRmid.key)low=mid+1;low=mid+1;插入位置在后半部分中插入位置在后

35、半部分中 else high=mid-1;/else high=mid-1;/插入位置在前半部分中插入位置在前半部分中 for(j=i-1;j=high+1;-j)/high+1 for(j=i-1;j=high+1;-j)/high+1为插入位置为插入位置 Rj+1=Rj;/Rj+1=Rj;/后移元素，空出插入位置后移元素，空出插入位置 Rhigh+1=R0;/Rhigh+1=R0;/将元素插入将元素插入 第23页，共46页，编辑于2022年，星期六【例【例10-2】待排序记录的关键字为：待排序记录的关键字为：28，13，72，85，39，41，6，20，在前，在前7个记录都已排好序的基础上

36、，采用折半插入第个记录都已排好序的基础上，采用折半插入第8个记录的比较个记录的比较过程如图过程如图10-2所示。所示。第24页，共46页，编辑于2022年，星期六第25页，共46页，编辑于2022年，星期六 折半插入排序仅减少了关键字间的比较次数，折半插入排序仅减少了关键字间的比较次数，但记录的移动次数不变。因此折半插入排序的时但记录的移动次数不变。因此折半插入排序的时间复杂度仍为间复杂度仍为O(nO(n2 2)。折半插入排序的空间复杂。折半插入排序的空间复杂度与直接插入排序相同。折半插入排序也是度与直接插入排序相同。折半插入排序也是一个稳定的排序方法。一个稳定的排序方法。第26页，共46页，

37、编辑于2022年，星期六2.2路插入排序路插入排序2路插入排序是在折半插入排序的基础上再改进，其目的是减少排序过程路插入排序是在折半插入排序的基础上再改进，其目的是减少排序过程中移动记录的次数，但为此需要中移动记录的次数，但为此需要n个记录的辅助空间。个记录的辅助空间。具体做法如下：设一个和具体做法如下：设一个和L.r同类型的数组同类型的数组d，然后从，然后从L.r中第中第2个个记录起依次插入到记录起依次插入到d1之前和之后的有序序列中。之前和之后的有序序列中。先将待插入记录的关键字和先将待插入记录的关键字和d1的关键字相比较，若的关键字相比较，若L.ri.keyd1.key，则将，则将L.r

38、i插入到插入到d1之前的有序表中。之前的有序表中。反之，将反之，将L.ri插入到插入到d1之后的有序表中。之后的有序表中。在实现算法时，可将在实现算法时，可将d看成一个循环向量，并设两个指针看成一个循环向量，并设两个指针first和和final分别指示排序过程中得到的有序序列中的第一个记录和最后分别指示排序过程中得到的有序序列中的第一个记录和最后一个记录在一个记录在d中的位置。中的位置。第27页，共46页，编辑于2022年，星期六第28页，共46页，编辑于2022年，星期六第29页，共46页，编辑于2022年，星期六第30页，共46页，编辑于2022年，星期六2-路插入排序只能减少移动记录的次

39、数，而不能绝对避免移动记路插入排序只能减少移动记录的次数，而不能绝对避免移动记录。当录。当L.r1的待排序记录中关键字最小或最大的记录时，的待排序记录中关键字最小或最大的记录时，2-路路插入排序就完全失去它的优越性。插入排序就完全失去它的优越性。因此，若希望在排序过程中不移动记录，只有改变存储结构，进行表因此，若希望在排序过程中不移动记录，只有改变存储结构，进行表插入排序插入排序3.表插入排序表插入排序#define SIZE 100 /静态链表容量静态链表容量Typedef struct RcdType rc;/记录项记录项int next;/指针项指针项SLNode;/表结点类型表结点类型

40、第31页，共46页，编辑于2022年，星期六typedef structSLNode rSIZE;/0号单元为表头结点号单元为表头结点int length;/链表当前长度；链表当前长度；SLinkListType;/静态链表类型静态链表类型设数组下标为设数组下标为“0”的分量为表头结点，并令表头结点记录的关键字的分量为表头结点，并令表头结点记录的关键字区最大整数区最大整数MAXINT。表插入排序的过程描述如下：首先将静态链表中数组下标为表插入排序的过程描述如下：首先将静态链表中数组下标为“1”的分量（结点）和表头结点构成一个循环链表，然后依次将下标为的分量（结点）和表头结点构成一个循环链表，然

41、后依次将下标为“2”至至“n”的分量（结点）按记录关键字非递减有序插入到循环的分量（结点）按记录关键字非递减有序插入到循环链表中链表中第32页，共46页，编辑于2022年，星期六第33页，共46页，编辑于2022年，星期六第34页，共46页，编辑于2022年，星期六第35页，共46页，编辑于2022年，星期六第36页，共46页，编辑于2022年，星期六表插入排序的基本操作仍为将一个记录插入到已经排好序的有序表中，和表插入排序的基本操作仍为将一个记录插入到已经排好序的有序表中，和直接插入排序相比，不同之处仅是以修改直接插入排序相比，不同之处仅是以修改2n次指针代替移动记录，排序过次指针代替移动记

42、录，排序过程中所需进行的关键字之间的比较次数相同。因此，表插入排序的时间复程中所需进行的关键字之间的比较次数相同。因此，表插入排序的时间复杂度仍为杂度仍为O(n2)。表插入排序的结果只是求得一个有序表，则只能进行对它顺序查表插入排序的结果只是求得一个有序表，则只能进行对它顺序查找，不能进行随机查找，为了实现有序表的折半查找，尚需对记找，不能进行随机查找，为了实现有序表的折半查找，尚需对记录进行重新排列。录进行重新排列。第37页，共46页，编辑于2022年，星期六10.2.3 10.2.3 10.2.3 10.2.3 希尔排序希尔排序希尔排序希尔排序 希希 尔尔 排排 序序（shellshell

43、s s sortsort）又又 称称 缩缩 小小 增增 量量 排排 序序(Diminishing(Diminishing Increment Increment Sort)Sort)。它它是是希希尔尔（D.L.ShellD.L.Shell）于于19591959年年提提出出的的插插入入排排序序的的改改进进算算法法。如如前前所所述述，直直接接插插入入排排序序算算法法的的时时间间性性能能取取决决于于数数据据的的初初始始特特性性，一一般般情情况况下下，它它的的时时间间复复杂杂度度为为O(nO(n2 2)。但但是是当当待待排排序序列列为为正正序序或或基基本本有有序序时时，时时间间复复杂杂度度则则为为O(

44、n)O(n)。因因此此，若若能能在在一一次次排排序序前前将将排排序序序序列列调调整整为为基基本本有有序序，则则排排序序的的效效率率就就会会大大大大提提高。正是基于这样的考虑，希尔提出了改进的插入排序方法。高。正是基于这样的考虑，希尔提出了改进的插入排序方法。希尔排序的基本思想是：先将整个待排记录序列分割成若干小组（子希尔排序的基本思想是：先将整个待排记录序列分割成若干小组（子序列），分别在组内进行直接插入排序，待整个序列中的记录序列），分别在组内进行直接插入排序，待整个序列中的记录“基本基本有序有序”时，再对全体记录进行一次直接插入排序。希尔排序的具体步时，再对全体记录进行一次直接插入排序。希

45、尔排序的具体步骤如下：骤如下：第38页，共46页，编辑于2022年，星期六（1 1）首首先先取取一一个个整整数数d d1 1nn，称称之之为为增增量量，将将待待排排序序的的记记录录分分成成d d1 1个个组组，凡凡是是距距离离为为d d1 1倍倍数数的的记记录录都都放放在在同同一一个个组组，在在各各组组内内进进行行直直接接插插入入排排序序，这这样样的的一一次次分分组组和和排排序序过过程程称称为为一一趟希尔排序。趟希尔排序。【例例10-310-3】设设有有一一个个待待排排序序的的序序列列有有1010个个记记录录，它它们们的的关关键键字字分分别别为为5858，4646，7272，9595，8484

46、，25 25，3737，5858，6363，12 12，用用希希尔尔排排序序法法进进行行排排序。序。【解】图【解】图10-310-3给出了希尔排序的整个过程，用同一连线上的关键字表示给出了希尔排序的整个过程，用同一连线上的关键字表示其所属的记录在同一组。为区别具有相同关键字其所属的记录在同一组。为区别具有相同关键字5858的不同记录，用下划的不同记录，用下划线标记后一个记录的关键字。线标记后一个记录的关键字。（2）再设置另一个新的增量）再设置另一个新的增量d2d1，采用与上述相同的方法继续，采用与上述相同的方法继续进行分组和排序过程。进行分组和排序过程。（3）继续取）继续取di+10)/通过增

47、量控制排序的执行过程通过增量控制排序的执行过程 for(i=d;i=0)if(Rj.keyRj+d.key)temp=Rj;/Rj与与Rj+d交换交换 Rj=Rj+d;Rj+d=temp;j=j-d;/j /j前移前移 else j=-1;d=d2;/递减增量递减增量d d 第44页，共46页，编辑于2022年，星期六从希尔排序过程可以看到：从希尔排序过程可以看到：（1 1）算法中约定初始增量）算法中约定初始增量d d1 1为已知；为已知；（2）算法中采用简单的取增量值的方法，从第二次起）算法中采用简单的取增量值的方法，从第二次起取增量值为其前次增量值的一半。在实际应用中，可取增量值为其前次增

48、量值的一半。在实际应用中，可能有多种取增量的方法，并且不同的取值方法对算法能有多种取增量的方法，并且不同的取值方法对算法的时间性能有一定的影响，因而的时间性能有一定的影响，因而一种好的取增量的方法一种好的取增量的方法是改进希尔排序算法时间性能的关键。是改进希尔排序算法时间性能的关键。第45页，共46页，编辑于2022年，星期六（3）希尔排序开始时增量较大，分组较多，每组的记录数较少，）希尔排序开始时增量较大，分组较多，每组的记录数较少，故各组内直接插入过程较快。随着每一趟中增量故各组内直接插入过程较快。随着每一趟中增量di逐渐缩小，分逐渐缩小，分组数逐渐减少，虽各组的记录数目逐渐增多，但由于已

49、经按组数逐渐减少，虽各组的记录数目逐渐增多，但由于已经按di-1作为作为增量排过序，使序列表较接近有序状态，所以新的一趟排序过程也较快。增量排过序，使序列表较接近有序状态，所以新的一趟排序过程也较快。因此，希尔排序在效率上较直接插入排序有较大的改进。希尔排序的时因此，希尔排序在效率上较直接插入排序有较大的改进。希尔排序的时间复杂度约为间复杂度约为O(n 1.3)，它实际所需的时间取决于各次排序时增量的取值。，它实际所需的时间取决于各次排序时增量的取值。大量研究证明，若增量序列取值较合理，希尔排序时关键字比较次数和大量研究证明，若增量序列取值较合理，希尔排序时关键字比较次数和记录移动次数约为记录移动次数约为O(nlog2n)2。由于其时间复杂度分析较复杂，在此。由于其时间复杂度分析较复杂，在此不做讨论不做讨论。注：希尔排序会使关键字相同的记录交换相对位置，所以希尔排序注：希尔排序会使关键字相同的记录交换相对位置，所以希尔排序是不稳定的。是不稳定的。第46页，共46页，编辑于2022年，星期六