数据结构第讲哈希表和插入排序幻灯片.ppt

数据结构第讲哈希表和插入排序第1页，共58页，编辑于2022年，星期六9.3.1 9.3.1 什么是哈希表什么是哈希表哈希表技术的主要目标是提高查找效率。哈希表技术的主要目标是提高查找效率。1.1.哈希函数哈希函数：根据关键字直接计算出元素所在位置的函数。根据关键字直接计算出元素所在位置的函数。例例：设哈希函数为：设哈希函数为：H(K)=K/3+1H(K)=K/3+1，则构造关键字序列，则构造关键字序列为为 1 1、2 2、5 5、9 9、1111、1313、1616、2121、27 27 的散列表（哈希的散列表（哈希表）为：表）为：序号序号12345678910H(K)15913162127211第2页，共58页，编辑于2022年，星期六2.2.冲突冲突 两个不同的关键字具有相同的存储位置。两个不同的关键字具有相同的存储位置。序号序号12345678910H(K)15913162127211第3页，共58页，编辑于2022年，星期六3.3.哈希表哈希表 根据设定的哈希函数根据设定的哈希函数 H(key)H(key)和处理冲突的方法将和处理冲突的方法将一组关键字映象到一个有限的连续的地址集（区间）一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的上，并以关键字在地址集中的“象象”作为记录在表中作为记录在表中的存储位置，这种表便称为的存储位置，这种表便称为哈希表哈希表，这一映象过程，这一映象过程称为称为哈希造表哈希造表或或散列散列，所得存储位置称为，所得存储位置称为哈希地址哈希地址或或散列地址散列地址。第4页，共58页，编辑于2022年，星期六 在哈希存储中，若发生冲突，则必须采取特殊的方法来解决冲突在哈希存储中，若发生冲突，则必须采取特殊的方法来解决冲突问题，才能使哈希查找能顺利进行。虽然冲突不可避免，但发生冲突问题，才能使哈希查找能顺利进行。虽然冲突不可避免，但发生冲突的可能性却与三个方面因素有关。的可能性却与三个方面因素有关。(1)(1)装填因子装填因子；装填因子是指哈希表中己存入的元素个数装填因子是指哈希表中己存入的元素个数 n n 与哈希表的大小与哈希表的大小 m m 的比值，即的比值，即=n/m=n/m（=1 724+518+69=724+518+69=13111311第11页，共58页，编辑于2022年，星期六6.6.随机数法随机数法 选择一个随机函数，取关键字的随机函数值为它的选择一个随机函数，取关键字的随机函数值为它的哈希地址，即哈希地址，即H(key)=random(key)H(key)=random(key)，其中，其中randomrandom为随机为随机函数。函数。通常，当关键字长度不等时采用此法构造哈希通常，当关键字长度不等时采用此法构造哈希函数较恰当。函数较恰当。第12页，共58页，编辑于2022年，星期六实际工作中需视不同情况采用不同的哈希函数。实际工作中需视不同情况采用不同的哈希函数。通常考虑通常考虑的因素：的因素：(1)(1)计算哈希函数所需时间计算哈希函数所需时间(包括硬件指令的因素包括硬件指令的因素)；(2)(2)关键字的长度；关键字的长度；(3)(3)哈希表的大小；哈希表的大小；(4)(4)关键字的分布情况；关键字的分布情况；(5)(5)记录的查找频率。记录的查找频率。第13页，共58页，编辑于2022年，星期六第第9 9章章 查找查找9.1 9.1 静态查找表静态查找表9.2 9.2 动态查找表动态查找表9.3 9.3 哈希表哈希表 9.3.1 9.3.1 什么是哈希表什么是哈希表 9.3.2 9.3.2 哈希函数的构造方法哈希函数的构造方法 9.3.3 9.3.3 处理冲突的方法处理冲突的方法 9.3.4 9.3.4 哈希表的查找及其分析哈希表的查找及其分析第14页，共58页，编辑于2022年，星期六9.3.3 9.3.3 处理冲突的方法处理冲突的方法1.1.开放地址法开放地址法 开开放放地地址址就就是是表表中中尚尚未未被被占占用用的的地地址址，当当新新插插入入的的记记录录所所选选地址已被占用时，即转而寻找其它尚开放的地址。地址已被占用时，即转而寻找其它尚开放的地址。（1 1）线性探测法）线性探测法 设设散散列列函函数数 H H（K K）=K=K mod mod m m（m m为为表表长长），若若发发生生冲冲突突，则则沿沿着着一一个个探探查查序序列列逐逐个个探探查查，那那么么，第第i i次次计计算算冲冲突突的的散散列列地址为：地址为：H Hi i=(H(K)+d=(H(K)+di i)mod m (d)mod m (di i=1,2,m-1)=1,2,m-1)第15页，共58页，编辑于2022年，星期六例例 关键码集为关键码集为 47 47，7 7，2929，1111，1616，9292，2222，8 8，33，设：设：哈希表表长为哈希表表长为m=11m=11；哈希函数为哈希函数为Hash(key)=key mod 11Hash(key)=key mod 11；拟用拟用线性探测法线性探测法线性探测法线性探测法处理冲突。建哈希表：处理冲突。建哈希表：0 1 2 3 4 5 6 7 8 9 100 1 2 3 4 5 6 7 8 9 1047477 7292911111616929222228 83 3第16页，共58页，编辑于2022年，星期六线性探测法的优点：线性探测法的优点：只要哈希表未被填满，保证能找到只要哈希表未被填满，保证能找到一个空地址单元存放有冲突的元素；一个空地址单元存放有冲突的元素；线性探测法的缺点：线性探测法的缺点：可能使第可能使第i i 个哈希地址的同义词存个哈希地址的同义词存入第入第i+1 i+1 个哈希地址，这样本应存入第个哈希地址，这样本应存入第i+1i+1个哈个哈希地址的元素变成了第希地址的元素变成了第i+2i+2个哈希地址的同义词，个哈希地址的同义词，因此，可能出现很多元素在相邻的哈希地址上因此，可能出现很多元素在相邻的哈希地址上“堆积堆积”起来，大大降低了查找效率。起来，大大降低了查找效率。可采用可采用二次探测法二次探测法二次探测法二次探测法或或或或伪随机探测法伪随机探测法伪随机探测法伪随机探测法，以改善以改善“堆积堆积”问题。问题。第17页，共58页，编辑于2022年，星期六1.1.开放地址法开放地址法（2 2）二次探测法）二次探测法 二次探测法对应的探查地址序列的计算公式为：二次探测法对应的探查地址序列的计算公式为：H Hi i=(H(k)+d=(H(k)+di i)mod m)mod m 其中其中di i=1=12 2,-1-12 2,2 22 2,-2-22 2,j j2 2,-j-j2 2 (jm/2)(jm/2)。第18页，共58页，编辑于2022年，星期六0 1 2 3 4 5 6 7 8 9 10112234792167298若若d di i伪随机序列，就称为伪随机探测法伪随机序列，就称为伪随机探测法例例 关键码集为关键码集为 47 47，7 7，2929，1111，1616，9292，2222，8 8，33，设：设：哈希表表长为哈希表表长为m=11m=11；哈希函数为哈希函数为Hash(key)=key mod 11Hash(key)=key mod 11；拟用二次探测法处理冲突。建哈希表如下：拟用二次探测法处理冲突。建哈希表如下：H Hi i=(H(k)+d=(H(k)+di i)mod m)mod m其中其中d di i=1=12 2,-1-12 2,2 22 2,-2-22 2,j j2 2,-j-j2 2 (jm/2)(jm/2)第19页，共58页，编辑于2022年，星期六2.2.链地址法链地址法优点优点：插入、删除方便。：插入、删除方便。缺点缺点：占用存储空间多。：占用存储空间多。基本思想：基本思想：将具有相同哈希地址的记录链成一个单链表，将具有相同哈希地址的记录链成一个单链表，m m个哈希地址就设个哈希地址就设 m m个单链表个单链表，然后用一个数组将，然后用一个数组将m m个个单链表的表头指针存储起来，形成一个动态的结构。单链表的表头指针存储起来，形成一个动态的结构。第20页，共58页，编辑于2022年，星期六例：例：设设 47,7,29,11,16,92,22,8,3,50,37,89 47,7,29,11,16,92,22,8,3,50,37,89 的哈希函数为：的哈希函数为：Hash(key)=key mod 11Hash(key)=key mod 11，用用拉链法拉链法处处理冲突，建表。理冲突，建表。0 1 2 3 4 5 6 7 8 91022118934737922971650810 有冲突的元素可以插在表尾有冲突的元素可以插在表尾,也可以插在表头。也可以插在表头。第21页，共58页，编辑于2022年，星期六3.3.再哈希再哈希法法H Hi i=RH=RHi i(key)(key)RH RHi i 均是不同的哈希函数，即在同义词产生地址冲突均是不同的哈希函数，即在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。不易产时计算另一个哈希函数地址，直到冲突不再发生。不易产生生“聚集聚集”，但是增加了计算时间。，但是增加了计算时间。4.4.建立一个公共溢出区建立一个公共溢出区第22页，共58页，编辑于2022年，星期六第第9 9章章 查找查找9.1 9.1 静态查找表静态查找表9.2 9.2 动态查找表动态查找表9.3 9.3 哈希表哈希表 9.3.1 9.3.1 什么是哈希表什么是哈希表 9.3.2 9.3.2 哈希函数的构造方法哈希函数的构造方法 9.3.3 9.3.3 处理冲突的方法处理冲突的方法 9.3.4 9.3.4 哈希表的查找及其分析哈希表的查找及其分析第23页，共58页，编辑于2022年，星期六9.3.4 9.3.4 哈希表的查找及其分析哈希表的查找及其分析 散列表的目的主要是用于快速查找。散列表的目的主要是用于快速查找。在在建建表表时时采采用用何何种种散散列列函函数数及及何何种种解解决决冲冲突突的的办办法法，在在查查找找时时，也也采采用用同同样样的的散散列列函函数数及及解解决冲突的办法。决冲突的办法。第24页，共58页，编辑于2022年，星期六例：例：设有一组关键字设有一组关键字 19,01,23,14,55,20,19,01,23,14,55,20,84,27,68,11,10,77 84,27,68,11,10,77，采用哈希函数为：，采用哈希函数为：H H（k k）=k mod=k mod 1313。采用开放地址的线性探测法解决冲突，试。采用开放地址的线性探测法解决冲突，试在在0 01818的散列地址空间中，对该关键字序列构造哈希表。的散列地址空间中，对该关键字序列构造哈希表。解：依题意解：依题意 m=19 m=19，得到线性探测法对应的探查地址序，得到线性探测法对应的探查地址序列计算公式为：列计算公式为：di=(H(k)+j)mod di=(H(k)+j)mod 1919;j=1,2,18;j=1,2,18 其计算函数如下：其计算函数如下：第25页，共58页，编辑于2022年，星期六H(19)=19 mod 13=6H(01)=01 mod 13=1H(23)=23 mod 13=10H(14)=14 mod 13=1(冲突冲突)H(14)=(1+1)mod 19=2H(55)=55 mod 13=3H(20)=20 mod 13=7H(84)=84 mod 13=6(冲突冲突)H(84)=(6+1)mod 19=7(冲突冲突)H(84)=(6+2)mod 19=8H(27)=27 mod 13=1（冲突）（冲突）H(27)=(1+1)mod 19=2(冲突冲突)H(27)=(1+2)mod 19=3(冲突冲突)H(27)=(1+3)mod 19=40123456789 10 11 12 13 14 15 16 17 181919,01,23,14,55,20,84,27,68,11,10,770123145520842777101168 第26页，共58页，编辑于2022年，星期六哈希查找的性能分析哈希查找的性能分析 哈哈希希查查找找按按理理论论分分析析，它它的的时时间间复复杂杂度度应应为为O(1)O(1)，它它的的平平均均查查找找长长度度应应为为ASL=1ASL=1，但但实实际际上上由由于于冲冲突突的的存存在在，它它的的平平均均查查找找长长度度将将会会比比1 1大大。下下面将分析几种方法的平均查找长度。面将分析几种方法的平均查找长度。第27页，共58页，编辑于2022年，星期六1.1.线性探查法的性能分析线性探查法的性能分析 由由于于线线性性探探查查法法解解决决冲冲突突是是线线性性地地查查找找空空闲闲位位置置的的，平平均均查查找找长长度度与与表表的的大大小小m m无无关关，只只与与所所选选取取的哈希函数的哈希函数H H及装填因子及装填因子的值和该处理方法有关。的值和该处理方法有关。这时的成功的平均查找长度为：这时的成功的平均查找长度为：ASL=(1+1/(1-)/2 ASL=(1+1/(1-)/2第28页，共58页，编辑于2022年，星期六2.2.链地址法查找的性能分析链地址法查找的性能分析 由于链地址法查找就是在单链表上查找，查找由于链地址法查找就是在单链表上查找，查找单链表中第一个结点的次数为单链表中第一个结点的次数为1 1，第二个结点次数，第二个结点次数为为2 2，其余依次类推。，其余依次类推。平均查找长度：平均查找长度：ASL=1+/2 ASL=1+/2第29页，共58页，编辑于2022年，星期六例例：给给定定关关键键字字序序列列1111，7878，1010，1 1，3 3，2 2，4 4，2121，试试分分别别用用顺顺序序查查找找、二二分分查查找找、二二叉叉排排序序树树查查找找、平平衡衡二二叉叉树树查查找找、哈哈希希查查找找(用用线线性性探探查查法法和和拉拉链链法法)来来实实现现查查找找，试试画画出出它它们们的的对对应应存存储储形形式式(顺顺序序查查找找的的顺顺序序表表，二二分分查查找找的的判判定定树树，二二叉叉排排序序树树查查找找的的二二叉叉排排序序树树及及平平衡衡二二叉叉树树查查找找的的平平衡衡二二叉叉树树，两两种种哈哈希希查查找找的的哈哈希希表表)，并并求求出出每每一一种种查查找找的的成成功功平平均均查查找找长长度度。设设哈哈希希函函数数为为：H(k)=k mod 11H(k)=k mod 11，哈希表表长，哈希表表长m=11m=11。第30页，共58页，编辑于2022年，星期六顺序查找的顺序表（一维数组）顺序查找的顺序表（一维数组）由图可得：顺序查找的成功平均查找长度为由图可得：顺序查找的成功平均查找长度为 ASL=(1+2+3+4+5+6+7+8)/8=4.5 ASL=(1+2+3+4+5+6+7+8)/8=4.5第31页，共58页，编辑于2022年，星期六二分查找的判定树二分查找的判定树（中序序列为从小到大排列的有序（中序序列为从小到大排列的有序序列）序列）由图可得：二分查找的成功平均查找长度为由图可得：二分查找的成功平均查找长度为 ASL=(1+2*2+3*4+4)/8=2.625 ASL=(1+2*2+3*4+4)/8=2.625第32页，共58页，编辑于2022年，星期六二叉排序树二叉排序树（关键字顺序已确定，该二叉排序树应唯一）如图（关键字顺序已确定，该二叉排序树应唯一）如图(a)(a)所示，所示，平衡二叉树（关键字顺序已确定，该平衡二叉树也应该是唯一的），平衡二叉树（关键字顺序已确定，该平衡二叉树也应该是唯一的），如图如图(b)(b)所示。所示。由图由图(a)(a)可得：二叉排序树查找的成功平均查找长度为可得：二叉排序树查找的成功平均查找长度为 ASL=(1+2*2+3*2+4+5*2)/9=3.125 ASL=(1+2*2+3*2+4+5*2)/9=3.125由图由图(b)(b)可得：平衡二叉树的成功平均查找长度为可得：平衡二叉树的成功平均查找长度为 ASL=(1+2*2+3*3+4*2)/8=2.75 ASL=(1+2*2+3*3+4*2)/8=2.75 11 10 1 3 2 4 78 21 3 1 11 2 10 4 78 21(a)二叉排序树二叉排序树 (b)平衡二叉树平衡二叉树第33页，共58页，编辑于2022年，星期六线性探查法解决冲突的哈希表如图所示。线性探查法解决冲突的哈希表如图所示。由图可得：线性探查法的成功平均查找长度为由图可得：线性探查法的成功平均查找长度为 ASL=ASL=（1+1+2+1+3+2+8+11+1+2+1+3+2+8+1）/8=2.375/8=2.375第34页，共58页，编辑于2022年，星期六链地址法解决冲突的哈希表如图所示。链地址法解决冲突的哈希表如图所示。由图可得：链地址法的成功平均查找长度为由图可得：链地址法的成功平均查找长度为 ASL=(1*6+2*2)/8=1.25 ASL=(1*6+2*2)/8=1.25第35页，共58页，编辑于2022年，星期六小结小结 1.1.掌握查找的基本概念；掌握查找的基本概念；2.2.熟练掌握静态查找表的查找算法思想并灵活应用；熟练掌握静态查找表的查找算法思想并灵活应用；3.3.熟练掌握动态查找表的特点以及二叉排序树、平衡熟练掌握动态查找表的特点以及二叉排序树、平衡二叉树的各种操作思想二叉树的各种操作思想 4.4.了解了解B-B-、B+B+树的概念及插入和删除操作；树的概念及插入和删除操作；5.5.熟练掌握哈希表的基本概念、哈希函数的构造熟练掌握哈希表的基本概念、哈希函数的构造方法和解决冲突的方法，并能计算平均查找长度。方法和解决冲突的方法，并能计算平均查找长度。第36页，共58页，编辑于2022年，星期六第第1010章章 内部排序内部排序10.1 10.1 排序的基本概念排序的基本概念10.2 10.2 插入排序插入排序10.3 10.3 交换排序交换排序10.4 10.4 选择排序选择排序10.5 10.5 归并排序归并排序10.6 10.6 基数排序基数排序10.7 10.7 各种内部排序方法的比较各种内部排序方法的比较第37页，共58页，编辑于2022年，星期六10.1 10.1 排序的基本概念排序的基本概念1.1.排序排序 设含有设含有n n个记录的文件个记录的文件R R1 1，R R2 2，RRn n，相应的关键字为，相应的关键字为K K1 1，K K2 2，KKn n，需确定一种排列，需确定一种排列P(1),P(2)P(n)P(1),P(2)P(n)使其相应的使其相应的关键字满足递增关键字满足递增(或递减或递减)关系：关系：K KP(1)P(1)KKP(2)P(2)KKP(n)P(n)或或 K KP(1)P(1)KKP(2)P(2)KKP(n)P(n)使上述文件成为一个按其关键字线性有序的文件使上述文件成为一个按其关键字线性有序的文件R RP(1)P(1)，R RP(2)P(2)，RRP(n)P(n)，这种运算就称为，这种运算就称为排序排序。将数据元素的无序序列调整为有序序列的过程。将数据元素的无序序列调整为有序序列的过程。第38页，共58页，编辑于2022年，星期六2.2.排序算法的稳定性排序算法的稳定性排序码（排序码（KeyKey）作为排序依据的记录中的一个属性。它可以是任何一作为排序依据的记录中的一个属性。它可以是任何一种可比的有序数据类型，它可以是记录的关键字，也可以种可比的有序数据类型，它可以是记录的关键字，也可以是任何非关键字。是任何非关键字。如果待排序的序列中，存在多个具有相同排序码的数如果待排序的序列中，存在多个具有相同排序码的数据元素，若经过排序这些数据元素的据元素，若经过排序这些数据元素的相对次序保持不变相对次序保持不变，则称这种则称这种排序算法是稳定的排序算法是稳定的，若经过排序，这些数据，若经过排序，这些数据元素的元素的相对次序发生了改变相对次序发生了改变，则称这种，则称这种排序算法是不稳排序算法是不稳定的定的。第39页，共58页，编辑于2022年，星期六3.3.内部排序与外部排序内部排序与外部排序内部排序内部排序 指当文件的数据量不太大时，全部信息放内存指当文件的数据量不太大时，全部信息放内存中处理的排序方法。中处理的排序方法。外部排序外部排序 当文件的数据量较大时，排序过程中需要在内、当文件的数据量较大时，排序过程中需要在内、外存之间不断地进行数据交换才能达到排序的目的，外存之间不断地进行数据交换才能达到排序的目的，这种排序称为外排序。这种排序称为外排序。第40页，共58页，编辑于2022年，星期六4.4.内部排序的方法内部排序的方法 内部排序的过程是一个逐步扩大记录的有序序内部排序的过程是一个逐步扩大记录的有序序长度的过程。在排序的过程中，参与排序的记录序长度的过程。在排序的过程中，参与排序的记录序列中存在两个区域：有序区和无序区。使有序区中列中存在两个区域：有序区和无序区。使有序区中记录的数目增加一个或几个的操作称为记录的数目增加一个或几个的操作称为一趟排序一趟排序。内部排序的方法很多，每种方法都有各自的优缺内部排序的方法很多，每种方法都有各自的优缺点，适合在不同的环境点，适合在不同的环境(如记录的初始排列状态等如记录的初始排列状态等)下下使用。使用。第41页，共58页，编辑于2022年，星期六排序排序简单排序方法，其时间复杂度为简单排序方法，其时间复杂度为O(nO(n2 2)先进排序方法，其时间复杂度为先进排序方法，其时间复杂度为O(nlogn)O(nlogn)基数排序，其时间复杂度为基数排序，其时间复杂度为O(dn)O(dn)按内部排序过程中所需的工作量来区分：按内部排序过程中所需的工作量来区分：第42页，共58页，编辑于2022年，星期六 插入类（直插排序、二分排序、希尔排序）插入类（直插排序、二分排序、希尔排序）交换类（冒泡排序、快速排序）交换类（冒泡排序、快速排序）选择类（直选排序、树型排序、堆排序）选择类（直选排序、树型排序、堆排序）归并类（二路归并排序、多路归并排序）归并类（二路归并排序、多路归并排序）分配类（多关键字排序、基数排序）分配类（多关键字排序、基数排序）按排序过程中依据的原则分按排序过程中依据的原则分排序排序第43页，共58页，编辑于2022年，星期六#define MAXSIZE 20 /#define MAXSIZE 20 /一个顺序表的最大长度一个顺序表的最大长度typedef int KeyType;/typedef int KeyType;/定义关键字为整数类型定义关键字为整数类型Typedef structTypedef struct KeyType key;/KeyType key;/关键字项关键字项 InfoType otherinfo;/InfoType otherinfo;/其他数据项其他数据项RedType;/RedType;/记录类型记录类型Typedef structTypedef struct RedType rMAXSIZE+1;/r0 RedType rMAXSIZE+1;/r0用作哨兵单元用作哨兵单元 int length;/int length;/顺序表长度顺序表长度SqList;/SqList;/顺序表类型顺序表类型第44页，共58页，编辑于2022年，星期六第第1010章章 内部排序内部排序10.1 10.1 排序的基本概念排序的基本概念10.2 10.2 插入排序插入排序10.3 10.3 交换排序交换排序10.4 10.4 选择排序选择排序10.5 10.5 归并排序归并排序10.6 10.6 基数排序基数排序10.7 10.7 各种内部排序方法的比较各种内部排序方法的比较第45页，共58页，编辑于2022年，星期六10.2 10.2 插入排序插入排序v 直接插入排序直接插入排序v 折半插入排序折半插入排序v 2-2-路插入排序路插入排序v 表插入排序表插入排序 v 希尔排序希尔排序第46页，共58页，编辑于2022年，星期六1 1）一趟直接插入排序的基本思想）一趟直接插入排序的基本思想 将记录将记录L.riL.ri插入到有序子序列插入到有序子序列L.r1.i-1L.r1.i-1中，使记录的有中，使记录的有序序列从序序列从L.r1.i-1L.r1.i-1变为变为L.r1.iL.r1.i。完成这个完成这个“插入插入”分三步进行：分三步进行：1 1查找查找L.riL.ri在有序子序列在有序子序列L.rL.r 1.i-11.i-1中的插入位置中的插入位置j j；2 2将将L.rL.r j.i-1j.i-1中的记录中的记录后移后移一个位置；一个位置；3 3将将L.rL.r ii复制复制到到L.rL.r jj的位置上。的位置上。整个排序过程整个排序过程进行进行n1n1趟插入趟插入，即：先将序列中的第，即：先将序列中的第1 1个记录着个记录着成一个有序的子序列，然后从第成一个有序的子序列，然后从第2 2个记录起逐个插入，直至整个个记录起逐个插入，直至整个序列变成接关键字非递减有序序列为止。序列变成接关键字非递减有序序列为止。1.1.直接插入排序直接插入排序第47页，共58页，编辑于2022年，星期六待排元素序列：待排元素序列：5353 27 36 15 69 42 27 36 15 69 42第一次排序：第一次排序：(27)(27)27 5327 53 36 15 69 42 36 15 69 42第二次排序：第二次排序：(36)(36)27 36 5327 36 53 15 69 42 15 69 42第三次排序：第三次排序：(53)(53)15 27 36 5315 27 36 53 69 42 69 42第四次排序：第四次排序：(69)(69)15 27 36 53 6915 27 36 53 69 42 42第五次排序第五次排序:(42)(42)15 27 36 42 53 6915 27 36 42 53 69 直接插入排序示例（插入操作要进行直接插入排序示例（插入操作要进行n-1n-1次）次）第48页，共58页，编辑于2022年，星期六2 2）直接插入排序算法描述）直接插入排序算法描述 void InsertionSort(void InsertionSort(SqListSqList&L)&L)/对记录序列对记录序列R1.L.lengthR1.L.length作直接插入排序。作直接插入排序。for(i=2;i=L.length;+i)for(i=2;i=L.length;+i)L.r0=L.ri;/L.r0=L.ri;/复制为监视哨复制为监视哨 for(j=i-1;L.r0.key L.rj.key;-j)for(j=i-1;L.r0.key L.rj.key;-j)L.rj+1=L.rj;/L.rj+1=L.rj;/记录后移记录后移 L.rj+1=L.r0;/L.rj+1=L.r0;/插入到正确位置插入到正确位置 /InsertSort/InsertSort第49页，共58页，编辑于2022年，星期六3 3）直接插入排序性能分析）直接插入排序性能分析 实现排序的基本操作有：实现排序的基本操作有：（1 1）“比较比较”关键字的大小关键字的大小 （2 2）“移动移动”记录记录对于直接插入排序：对于直接插入排序：最好情况最好情况“比较比较”次数：次数：n-1n-1；“移动移动”次数：次数：2(n-1)2(n-1)最坏的情况最坏的情况“比较比较”和和“移动移动”的次数均达到最大值，分别为：的次数均达到最大值，分别为：(n+2)(n-1)/2(n+2)(n-1)/2；(n+4)(n-1)/2(n+4)(n-1)/2 由于待排记录序列是随机的，取上述二值的平均值。所以直接插由于待排记录序列是随机的，取上述二值的平均值。所以直接插入排序的入排序的时间复杂度为时间复杂度为 O(n O(n2 2)。直接插入排序是直接插入排序是“稳定的稳定的”：关键码相同的两个记录，在：关键码相同的两个记录，在整个排序过程中，不会通过比较而相互交换。整个排序过程中，不会通过比较而相互交换。第50页，共58页，编辑于2022年，星期六2.2.折半插入排序折半插入排序1 1）基本思想）基本思想 考虑到考虑到 L.r1.i-1 L.r1.i-1 是按关键字有序的有序序列，是按关键字有序的有序序列，则可以利用则可以利用折半查找实现折半查找实现“L.r1L.r1i-1i-1中查找中查找 L.ri L.ri 的插入位置的插入位置”如此实现的插入排序为折半插入排如此实现的插入排序为折半插入排序。序。第51页，共58页，编辑于2022年，星期六(high36)(4253 )折半插入排序在寻找插入位置时，不是逐个比较而是利用折半插入排序在寻找插入位置时，不是逐个比较而是利用折半查找的原理寻找插入位置。待排序元素越多，改进效果越折半查找的原理寻找插入位置。待排序元素越多，改进效果越明显。明显。例：有例：有6 6个记录，前个记录，前5 5个已排序的基础上，对第个已排序的基础上，对第6 6个记录排序个记录排序。15 27 36 53 69 42 15 27 36 53 69 42 15 27 36 53 69 42 15 27 36 42 53 69 high mid low low high mid high low第52页，共58页，编辑于2022年，星期六void BinsertSort(SqList&L)void BinsertSort(SqList&L)int i,low,high,mid;int i,low,high,mid;for(i=2;i=L.length;+i)for(i=2;i=L.length;+i)L.r0=L.ri;L.r0=L.ri;low=1;high=i-1;low=1;high=i-1;While(low=high)While(low=high)mid=(low+high)/2;mid=(low+high)/2;if(L.r0.key L.rmid.key)high=mid-1;if(L.r0.key=low;for(j=i-1;j=low;j)L.rj+1=L.rj;j)L.rj+1=L.rj;L.rlow=L.r0;L.rlow=L.r0;2)2)折半插入排序算法折半插入排序算法第53页，共58页，编辑于2022年，星期六3)3)折半插入排序性能分析折半插入排序性能分析 折半插入排序折半插入排序减少了减少了关键字的关键字的比较比较次数，但记录的次数，但记录的移动次数不变移动次数不变，其时间复杂度与直接插入排序相同。，其时间复杂度与直接插入排序相同。折半插入排序是折半插入排序是“稳定的稳定的”第54页，共58页，编辑于2022年，星期六3.2-3.2-路插入排序路插入排序1 1）基本思想）基本思想 2-2-路插入排序是在折半插入排序的基础上改进的，路插入排序是在折半插入排序的基础上改进的，目的是减少排序过程中移动记录的次数，但为此需要目的是减少排序过程中移动记录的次数，但为此需要n n个记录的辅助空间。个记录的辅助空间。第55页，共58页，编辑于2022年，星期六2 2）具体做法）具体做法 另设一个和另设一个和 L.r L.r 同类型的数组同类型的数组d d，首先将，首先将 L.r1 L.r1 赋值给赋值给 d1 d1，并将，并将 d1 d1 看成是在排好序的序列中处于中间位置的看成是在排好序的序列中处于中间位置的记录，然后从记录，然后从 L.r L.r 中第中第 2 2 个记录起依次插入到个记录起依次插入到d1 d1 之前或之之前或之后的有序序列中。先将待插入记录的关键字和后的有序序列中。先将待插入记录的关键字和 d1 d1 的关键字的关键字进行比较。进行比较。若若 L.rid1.keyL.rid1.key，则将，则将 L.ri L.ri 插入到插入到 d1 d1 之前的有之前的有序表中。反之，插入到序表中。反之，插入到 d1 d1 之后的有序表中。之后的有序表中。第56页，共58页，编辑于2022年，星期六【初始关键字初始关键字】49 38 65 97 76 13 27 49 38 65 97 76 13 27 4949 排序过程中排序过程中d d 的状态如下：的状态如下：i=1:(49)i=1:(49)i=2:(49)i=2:(49)(38)(38)i=3:(49 i=3:(49 6565）（3838）i=4:(49 65 i=4:(49 65 9797）（3838）i=5:(49 65 i=5:(49 65 76 76 97 97）（3838）i=6:(49 65 76 97i=6:(49 65 76 97）（1313 38 38）i=7:(49 65 76 97i=7:(49 65 76 97）（13 13 2727 38 38）i=8:(49 i=8:(49 4949 65 76 97 65 76 97）（13 27 3813 27 38）finalfirst2 2路插入排序过程示例：路插入排序过程示例：firstfinalfinalfirstfinalfirstfinalfirstfinalfirstfinalfirstfinalfirst第57页，共58页，编辑于2022年，星期六3 3）2-2-路插入排序性能分析路插入排序性能分析 2-2-路插入排序只能减少移动记录的次数，而不能绝对路插入排序只能减少移动记录的次数，而不能绝对避免移动记录。避免移动记录。2-2-路插入排序中，移动记录的次数约为路插入排序中，移动记录的次数约为n n2 2/8/8。当当L.r1L.r1是待排序记录中关键字最小或最大的是待排序记录中关键字最小或最大的记录时，记录时，2-2-路插入排序就完全失去了它的优越性。路插入排序就完全失去了它的优越性。第58页，共58页，编辑于2022年，星期六