第三章_查找与排序技术

1、第三章第三章 查找与排序技术查找与排序技术第三章第三章 查找与排序技术查找与排序技术3.1 基本查找技术基本查找技术 查找：查找：在一个给定的数据结构中查找某个指定在一个给定的数据结构中查找某个指定的元素。的元素。 通常，根据不同的通常，根据不同的数据结构数据结构，应该采用不同的，应该采用不同的查找方法：查找方法： 顺序查找；顺序查找； 有序表的对分查找；有序表的对分查找； 分块查找。分块查找。3.1.1 顺序查找顺序查找 顺序查找（顺序搜索）：顺序查找（顺序搜索）：在线性表中查找指定在线性表中查找指定的元素。的元素。 顺序查找的基本方法：顺序查找的基本方法：从线性表的第一个元素从线性表的第一

2、个元素开始，依次将线性表中的元素与被查元素进行开始，依次将线性表中的元素与被查元素进行比较，若相等则表示找到（比较，若相等则表示找到（查找成功查找成功）；若线）；若线性表中的所有元素都与被查元素进行了比较但性表中的所有元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找到的元素都不相等，则表示线性表中没有要找到的元素（查找失败查找失败）。）。回顾回顾：举例说明举例说明 举例举例：设设L是包是包含含n个元素的一个元素的一维数组。对于指维数组。对于指定的输入定的输入x，如如果果x在数组中，在数组中，则顺序找到它第则顺序找到它第一次出现处的下一次出现处的下标；标； 如果如果x不在数不在数组中

3、，则以组中，则以下标下标0作为查作为查找结果。找结果。 算法算法：顺序搜索法（：顺序搜索法（Sequential Search）。）。输入：一维数组输入：一维数组L(1:n)，被查项被查项x。输出：第一次使输出：第一次使L(j)=x的的j，若若x不不在数组在数组L中，则输出中，则输出j=0。 j1 WHILE (jn)and(L(j)x) DO jj+1 IF jn THEN j0 OUTPUT j RETURN被访问的数组元素下标被访问的数组元素下标如果没有被访问如果没有被访问到数组尾部，且到数组尾部，且暂时没有发现元暂时没有发现元素值等于素值等于x。回顾回顾：平均性态分析平均性态分析 设被

4、查项设被查项x在数组在数组L中的概率为中的概率为q。当输入的当输入的x为为L(i)时，算法所做的比较次数为：时，算法所做的比较次数为： 1,1 ,)(ninniiiLT 1,11 ,)(niqninqiLp 再假设输入的再假设输入的x出现在数组中的每个位置上的出现在数组中的每个位置上的可能性是一样的，即可能性是一样的，即其中其中x=L(n+1)表示表示x不在数组不在数组L中的情况。中的情况。顺序查找的效率顺序查找的效率 如果线性表中的如果线性表中的第一个元素第一个元素就是被查找元素，就是被查找元素，只需要做一次比较就只需要做一次比较就查找成功查找成功； 如果被查的元素是线性表中的如果被查的元素

5、是线性表中的最后一个元素最后一个元素，或者被查元素根本不在线性表中，则需要与线或者被查元素根本不在线性表中，则需要与线性表中的所有元素进行比较（性表中的所有元素进行比较（最坏情况最坏情况）；）； 平均情况：平均情况：利用顺序查找法在线性表中查找一利用顺序查找法在线性表中查找一个元素，大约要与个元素，大约要与线性表中一半的元素线性表中一半的元素进行比进行比较。较。结论结论对于大的线性表来说，对于大的线性表来说，顺序查找的效率是很顺序查找的效率是很低低的。但在下列两种情况下也只能采用顺序的。但在下列两种情况下也只能采用顺序查找：查找：如果线性表为如果线性表为无序表无序表（表中元素的排列是无（表中元

6、素的排列是无序的），则不管是顺序存储结构还是链式存序的），则不管是顺序存储结构还是链式存储结构，都只能用顺序查找法；储结构，都只能用顺序查找法；1. 即使是即使是有序线性表有序线性表，如果采用链式存储结构如果采用链式存储结构，也只能用顺序查找。也只能用顺序查找。3.1.2 有序表的对分查找有序表的对分查找 有序表有序表：线性表中的元素按值非递减或者非递增线性表中的元素按值非递减或者非递增排列。排列。 对分查找的过程：对分查找的过程：将被查找关键字与将被查找关键字与线性表中间线性表中间的项目的项目进行比较，有三种可能：进行比较，有三种可能： 若被查关键字与表中间的项目相等，则查到，过若被查关键字

7、与表中间的项目相等，则查到，过程结束；程结束； 若被查关键字大于表中间的项目，则取表的后半若被查关键字大于表中间的项目，则取表的后半部分作为新表再去查找；部分作为新表再去查找；1. 若被查关键字小于表中间的项目，则取表的前半若被查关键字小于表中间的项目，则取表的前半部分作为新表再去查找。部分作为新表再去查找。升序升序降序降序查找成功！查找成功！在后半部分查找！在后半部分查找！在前半部分查找！在前半部分查找！减半递推！减半递推！举例：在下列数据中查找元素举例：在下列数据中查找元素2626010205091113161921262731lowhighmiddlelowhighmiddlelowmi

8、ddle high第一次第二次第三次对分法查找优点:平均检索长度小，为log2nhigh第四次#include/using namespace std;template class SL_List private:int mm;int nn;T *v; public:/只定义对象名只定义对象名SL_List() mm=0; nn=0; return; int search_SL_List(T); /顺序有序表查找顺序有序表查找顺序有序表的长度顺序有序表的长度顺序有序表的对分查找顺序有序表的对分查找/顺序有序表查找顺序有序表查找template int SL_List:search_SL_Lis

9、t( T x ) int i, j, k; i = 1; j = nn; while (ix ) j = k - 1; /取前半部分取前半部分 else i = k + 1; /取后半部分取后半部分 return (-1); /找不到返回找不到返回查找范围从数组中第查找范围从数组中第i个元素开个元素开始，到第始，到第j个元素结束。个元素结束。找到表中间元素找到表中间元素vk-1下一次查找从第下一次查找从第i个元素开始，到第个元素开始，到第k-1个元素结束。个元素结束。下一次查找从第下一次查找从第k+1个元素开始，个元素开始，到第到第j个元素结束。个元素结束。时间效率分析时间效率分析 对分查找是

10、根据每次试探的结果将线性表的规对分查找是根据每次试探的结果将线性表的规模减半，并有规则地括出可能包含被查项目的模减半，并有规则地括出可能包含被查项目的部分。部分。 最坏情况：最坏情况：对查找需要的比较次数为对查找需要的比较次数为 n为线性表的长度。为线性表的长度。 局限性：局限性：只适用于只适用于有序表有序表，且只限于，且只限于顺序存储顺序存储结构结构。 1log2 n3.1.3 分块查找分块查找 分块查找又称分块查找又称索引查找索引查找，是顺序查找的一种改，是顺序查找的一种改进方法，用于在进方法，用于在“分块有序分块有序”表表中进行查找。中进行查找。 “分块有序分块有序”表表：将长度为将长度

11、为n线性表线性表L分成分成m个个子表（各子表的长度可以不等，也可以相等），子表（各子表的长度可以不等，也可以相等），且且后一个子表中的每一项均大于前一个子表中后一个子表中的每一项均大于前一个子表中的所有项的所有项。分块有序表分块有序表 分块有序表分块有序表的结构可以分为两部分：的结构可以分为两部分：(1)(1)线性表本身采用线性表本身采用顺序存储结构顺序存储结构也可以采用也可以采用链式链式存储结构存储结构。(2)(2)再建立一个再建立一个索引表索引表。在索引表中，对线性表的。在索引表中，对线性表的每个子表建立一个每个子表建立一个索引结点索引结点，每个结点包括两，每个结点包括两个域：一是个域：一

12、是数据域数据域，用于存放对应子表中的，用于存放对应子表中的最最大元素值大元素值；二是；二是指针域指针域，用于指示对应子表的，用于指示对应子表的第一个元素在整个线性表中的第一个元素在整个线性表中的序号序号或者或者地址地址。图图3.1 分块有序表例（第分块有序表例（第161页）页）1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1822 12 13 08 09 20 33 42 44 38 24 46 60 58 74 47 86 53分析分析 根据分块有序表的结构，其查找过程可以分以根据分块有序表的结构，其查找过程可以分以下两步进行：下两步进行：(1)(1)首

13、先查找索引表，以便确定被查元素所在的首先查找索引表，以便确定被查元素所在的子表。由于索引表数据域中的数据是有序的且子表。由于索引表数据域中的数据是有序的且顺序存储，因此可以采用顺序存储，因此可以采用对分查找对分查找。(2)(2)然后在相应的子表中用然后在相应的子表中用顺序查找法顺序查找法进行具体进行具体的查找。的查找。 结论：分块查找的效率介于对分查找和顺序查结论：分块查找的效率介于对分查找和顺序查找之间。找之间。顺序查找、折半查找，这些查找技术都是通过一顺序查找、折半查找，这些查找技术都是通过一系列的给定值与关键码的比较，查找效率依赖于系列的给定值与关键码的比较，查找效率依赖于查找过程中进行

14、的给定值与关键码的比较次数。查找过程中进行的给定值与关键码的比较次数。1.1.查找操作要完成什么任务？查找操作要完成什么任务？待查值待查值k确定确定k在存储结构中的位置在存储结构中的位置2.2.我们学过哪些查找技术？这些查找技术的共性？我们学过哪些查找技术？这些查找技术的共性？在存储位置和关键码之间建立一个确定的对应关系在存储位置和关键码之间建立一个确定的对应关系3.3.能否不用比较，通过关键码直接确定存储位置？能否不用比较，通过关键码直接确定存储位置？例例1 1 假设有一个含有假设有一个含有8080个记录的查个记录的查 找表，记录的关键字均为两位找表，记录的关键字均为两位 的十进制数，则设有

15、存储记录的十进制数，则设有存储记录 的数组为：的数组为： ElemType hashtable100;ElemType hashtable100; 并令关键字为并令关键字为keykey的记录存的记录存 在数组的第在数组的第i i个分量个分量 hashtableihashtablei中。中。99995858575756560330220110i=f1(key)=key例例2 2 假设一组记录的关键字，则设假设一组记录的关键字，则设 有存储记录的数组为：有存储记录的数组为： ElemType hashtable26;ElemType hashtable26; 并令关键字为并令关键字为keykey的

16、记录存的记录存 在数组的第在数组的第i i个分量个分量 hashtableihashtablei中。中。ZHAO25YI24XIAO23WU22GAO6CHEN2BAI10 i = f2(key) = 关键字的第一个字母的关键字的第一个字母的ASCII码码 A的的ASCII码码在存储位置和关键码之间建立一个确定的对应关系在存储位置和关键码之间建立一个确定的对应关系3.3.能否不用比较，通过关键码直接确定存储位置？能否不用比较，通过关键码直接确定存储位置？在存储位置和关键码之间建立一个确定的对应关系在存储位置和关键码之间建立一个确定的对应关系3.3.能否不用比较，通过关键码直接确定存储位置？能否

17、不用比较，通过关键码直接确定存储位置？关关键键码码集集合合ki riH( (ki) )H一一. .有关概念有关概念1 1、哈希函数、哈希函数用来定义记录的关键字与记录存储位用来定义记录的关键字与记录存储位置的对应关系的函数。其自变量是记置的对应关系的函数。其自变量是记录的关键字，函数值是记录存储位置录的关键字，函数值是记录存储位置3.2 3.2 哈希表哈希表关关键键码码集集合合ki riH( (ki) )H哈希函数哈希函数i=f1(key)=key一一. .有关概念有关概念 3.2 哈希表哈希表2 2、哈希地址、哈希地址由哈希函数求出的记录存储位置称由哈希函数求出的记录存储位置称为哈希地址为哈

18、希地址关关键键码码集集合合ki riH( (ki) )H哈希函数哈希函数哈希地址哈希地址一一. .有关概念有关概念3.2 哈希表哈希表3 3、哈希表、哈希表也叫散列表，是将记录按哈希函数也叫散列表，是将记录按哈希函数确定的位置存放而构成的表确定的位置存放而构成的表关关键键码码集集合合ki riH( (ki) )H哈希函数哈希函数哈希地址哈希地址散列表散列表数组数组散列技术仅仅是一种查找技术吗？散列技术仅仅是一种查找技术吗？散列既是一种查找技术，也是一种存储技术。散列既是一种查找技术，也是一种存储技术。 散列只是通过记录的关键码定位该记录，没散列只是通过记录的关键码定位该记录，没有完整地表达记录

19、之间的逻辑关系，所以，散列有完整地表达记录之间的逻辑关系，所以，散列主要是主要是面向查找面向查找的存储结构。的存储结构。散列是一种散列是一种完整的存储结构完整的存储结构吗？吗？3.2 哈希表哈希表一一. .有关概念有关概念3.2.1 哈希表的基本概念哈希表的基本概念1. 直接查找技术直接查找技术 设表的长度为设表的长度为n。如果存在一个如果存在一个函数函数ii(k)，对对于表中的任意一个于表中的任意一个元素元素的的关键字关键字k，满足以下满足以下条件：条件：(1)函数值函数值i的范围为：的范围为：1in；(2)对于任意的元素关键字对于任意的元素关键字k1k2，恒存在恒存在i(k1)i(k2)。

20、则称此表为则称此表为直接查找表直接查找表。 其中函数其中函数ii(k)称为关键字称为关键字k的的映象函数映象函数。直接查找技术直接查找技术 直接查找表中各元素的关键字直接查找表中各元素的关键字k与表项序号与表项序号i之之间存在着间存在着一一对应的关系一一对应的关系； 对直接查找表的查找，只需要根据对直接查找表的查找，只需要根据映像函数映像函数i=i(k)计算出待查关键字项目在表中的计算出待查关键字项目在表中的序号序号i即即可。可。 直接查找技术要求映像函数能使得表中任意两个直接查找技术要求映像函数能使得表中任意两个不同的关键字其映像函数值也不同（不同的关键字其映像函数值也不同（不允许元素不允许

21、元素冲突的存在冲突的存在）；但在实际应用中，这一条件很难）；但在实际应用中，这一条件很难满足。满足。 对于两个不同的关键字对于两个不同的关键字k1 k2有有i(k1)=i(k2)，发生发生了了元素冲突元素冲突，即，即两个不同元素需要存在在同一个两个不同元素需要存在在同一个存储单元中存储单元中。举例举例 例例3.2 将关键字序列将关键字序列(09，31，26，19，01，13，02，11，27，16，05，21)依次填入长度为依次填入长度为n12的表中。映象函数为的表中。映象函数为iINT(k/3)1。关键字关键字01和和02发生冲突：发生冲突：因为两个数值都想要存因为两个数值都想要存放在表的第

22、放在表的第1项中。项中。关键字关键字09和和11发生冲突：发生冲突：因为两个数值都想要存因为两个数值都想要存放在表的第放在表的第4项中。项中。分析分析 显然，当有元素发生冲突时，是无法进行直接显然，当有元素发生冲突时，是无法进行直接查找的。所以引入查找的。所以引入Hash表表的概念：的概念： 设表的长度为设表的长度为n。若存在一个映象函数若存在一个映象函数i=i(k)，对于表中任一元素的关键字对于表中任一元素的关键字k，满足满足1 i(k) n ，则称此表为则称此表为Hash表表。并称。并称i(k)为关键字为关键字k的的Hash码码。 Hash表中允许的冲突存在表中允许的冲突存在。如果在。如果

23、在Hash表中表中没有冲突存在，则没有冲突存在，则Hash表就成为直接查找表。表就成为直接查找表。分析分析2. Hash表表 处理表中元素的主要工作：处理表中元素的主要工作：(1)构造合适的构造合适的Hash码，以便尽量减少表中元素冲突码，以便尽量减少表中元素冲突的次数。的次数。(2)当表中元素发生冲突时，要进行适当的处理。当表中元素发生冲突时，要进行适当的处理。3. Hash码的构造码的构造 查找关键字为查找关键字为k的元素时，的元素时，计算计算Hash码码i(k)的工作量的工作量是影响效率的重要因素是影响效率的重要因素。 在实际构造在实际构造Hash码时，要考虑如下两方面的因素：码时，要考

24、虑如下两方面的因素：(1)使各关键字尽可能均匀地分布在使各关键字尽可能均匀地分布在Hash表中，即表中，即Hash码的均匀性要好，以便减少冲突发生的机会。码的均匀性要好，以便减少冲突发生的机会。(2)Hash码的计算要尽量简单。码的计算要尽量简单。一些简单的一些简单的Hash码构造方法码构造方法截段法截段法 分段叠加法分段叠加法 除法除法 乘法乘法 截段法截段法 因为关键字是一种基本的符号串，而在计算机中因为关键字是一种基本的符号串，而在计算机中就是一个经过编码的就是一个经过编码的二进制数字串二进制数字串。 截取法截取法：选取与关键字对应的数字串中的一段选取与关键字对应的数字串中的一段（一般选

25、取低位数）作为关键字的（一般选取低位数）作为关键字的Hash码。码。 有有80个记录，关键字为个记录，关键字为8位十进制数，哈希地位十进制数，哈希地址为址为2位十进制数。位十进制数。8 1 3 4 6 5 3 28 1 3 7 2 2 4 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8 1 3 3 8 9 6 78 1 3 6 8 5 3 78 1 4 1 9 3 5 5. 分析：分析： 只取只取8 只取只取1 只取只取3、4 只取只取2、7、5 数字分布近乎随机数字分布近乎随机所以：取所以：取任意两位或两位任意两位或两位 与另两位的叠加作哈希

26、地址与另两位的叠加作哈希地址举例举例: 关键字为关键字为 0442205864，哈希地址位数为，哈希地址位数为45 8 6 44 2 2 00 41 0 0 8 8H(key)=0088移位叠加移位叠加5 8 6 40 2 2 40 4 6 0 9 2H(key)=6092间界叠加间界叠加 分段叠加法分段叠加法 将关键字的编码串分割成若干段，然后把它们叠加将关键字的编码串分割成若干段，然后把它们叠加后再进行截段。后再进行截段。两种叠加处理的方法：两种叠加处理的方法：移位叠加：移位叠加：将分割后的几部分低位对齐相加；将分割后的几部分低位对齐相加；1.间界叠加：间界叠加：从一端沿分割界来回折送，然

27、后对齐相从一端沿分割界来回折送，然后对齐相加。加。 除法除法 imod(k，n) 其中其中k为关键字，为关键字，n为为Hash表的长度，而表的长度，而mod为为模余运算符模余运算符； 当当mod(k，n)=0时，取时，取i=n（本节规定）。本节规定）。 乘法乘法 imod(k*，n)一般取一般取0.618033988747，或，或0.6125423371，或，或0.6161616161。3.2.2 几种常用的几种常用的Hash表表1. 线性线性Hash表表 线性表是一种线性表是一种最简单的最简单的Hash表表。 设线性设线性Hash表的长度为表的长度为m，则对线性则对线性Hash表的表的查找过

28、程如下：查找过程如下：线性线性Hash表的填入表的填入 将关键字将关键字k及有关信息填入线性及有关信息填入线性Hash表的步骤如表的步骤如下：下：1)计算关键字计算关键字k的的Hash码码ii(k)。2)检查表中第检查表中第i项的内容：项的内容： 若第若第i项为空，则将关键字项为空，则将关键字k及有关信息填入该及有关信息填入该项；项； 若第若第i项不空，则令项不空，则令imod(i1，n)，转转2)继继续检查。续检查。 只要只要Hash表尚未填满，最终总可以找到一个空表尚未填满，最终总可以找到一个空项，将关键字项，将关键字k及有关信息填入到及有关信息填入到Hash表中。表中。线性线性Hash表

29、的表的冲突处理。冲突处理。 线性线性Hash表的取出表的取出 要在线性要在线性Hash表中取出关键字表中取出关键字k的元素，其步骤的元素，其步骤如下：如下：1)计算关键字计算关键字k的的Hash码码ii(k)。2)检查表中第检查表中第i项的内容：项的内容： 若第若第i项登记着关键字项登记着关键字k，则取出该项元素即可；则取出该项元素即可； 若第若第i项为空，则表示在项为空，则表示在Hash表中没有该关键表中没有该关键字的信息；字的信息； 若第若第i项不空，且登记的不是关键字项不空，且登记的不是关键字k，则令则令imod(i1，n)转转2)继续检查。继续检查。 例例3.3 将关键字序列将关键字序

30、列(09，31，26，19，01，13，02，11，27，16，05，21)依次填入长度为依次填入长度为n12的的线性线性Hash表中。表中。设设Hash码码为为iINT(k/3)1。表表3.2 线性线性Hash表表分析分析 线性线性Hash表的表的优点优点：简单。简单。 线性线性Hash表的表的缺点缺点：在线性在线性Hash表填入的过程中，当发生冲突时，首表填入的过程中，当发生冲突时，首先考虑的是下一项，因此，当先考虑的是下一项，因此，当Hash码的冲突较多码的冲突较多时，在线性时，在线性Hash表中会存在表中会存在“堆聚堆聚”现象现象，即许，即许多关键字被连续登记在一起，从而会降低查找效多

31、关键字被连续登记在一起，从而会降低查找效率。率。在线性在线性Hash表的填入过程中，处理冲突时会带来表的填入过程中，处理冲突时会带来新的冲突。线性新的冲突。线性Hash表的填入方法是表的填入方法是不顾后效不顾后效的。的。 n为为Hash表的长度，而表的长度，而m为为Hash表中实际存在的表中实际存在的关键字个数。关键字个数。 注意注意：Hash表的平均查找次数表的平均查找次数E不依赖于表的长不依赖于表的长度，而只与表的填满率有关。度，而只与表的填满率有关。 此公式只仅在知此公式只仅在知道表长道表长n和实际填和实际填放关键字个数放关键字个数m的的情况下有效！情况下有效！ 如果有一个确定如果有一个

32、确定Hash表，则要确定表，则要确定表的平均查找次数表的平均查找次数就必须要采用就必须要采用平均平均性态法性态法求取！求取！2. 随机随机Hash表表 当当Hash表的长度表的长度n为为2的乘幂的乘幂时（时（n=2k），），可以可以定义另一种定义另一种Hash表表随机随机Hash表表。 随机随机Hash表表与与线性线性Hash表表的不同之处在于：的不同之处在于：一旦发生元素冲突时，表项序号一旦发生元素冲突时，表项序号i的改变不是的改变不是采用加采用加1取模的方法，而是用某种取模的方法，而是用某种伪随机数伪随机数来来改变改变i值。值。 随机随机Hash表的填入表的填入 将关键字将关键字k及有关信

33、息填入随机及有关信息填入随机Hash表的步骤如下：表的步骤如下：1)计算关键字计算关键字k的的Hash码码i0i(k)。且令且令ii0。2)伪随机数序列初始化，令伪随机数序列初始化，令j1（即将取随机数指针即将取随机数指针指向伪随机数序列中的第指向伪随机数序列中的第1个随机数）。个随机数）。3)检查表中第检查表中第i项的内容：项的内容： 若第若第i项为空，则将关键字项为空，则将关键字k及有关信息填入该项；及有关信息填入该项； 若第若第i项不空，则令项不空，则令imod(i0RN(j)，n)，并令并令jj1（即将取随机数指针指向下一个随机数），即将取随机数指针指向下一个随机数），转转3)继续检查

34、。继续检查。 其中其中RN(j)表示伪随机数序列表示伪随机数序列RN中的中的第第j个随机数个随机数。伪随机数的产生伪随机数的产生 伪随机数序列伪随机数序列RN按下列方法产生：按下列方法产生： R1 FOR j1 TO n DO Rmod(5*R，4n) RN(j)INT(R/4) 如果表的长度如果表的长度n=16，则伪随机数序列则伪随机数序列RN(j)为：为：1，6，15，12，13，2，11，8，9，14，7，随机随机Hash表的表长表的表长 例例3.4 将关键字序列将关键字序列(09，31，26，19，01，13，02，11，27，16，05，21)依次填入长度为依次填入长度为n2416的

35、随机的随机Hash表中。表中。设设Hash码为码为iINT(k/3)1。伪随机数序列为：伪随机数序列为：1，6，15，12，13，2，11，8，9，14，7，4，5，10，3，0表表3.3 随机随机Hash表（第表（第169页）页） 随机随机Hash表的取出表的取出 要在随机要在随机Hash表中取出关键字表中取出关键字k的元素，其步的元素，其步骤如下：骤如下：1)计算关键字计算关键字k的的Hash码码i0i(k)。且令且令ii0。2)伪随机数序列初始化，令伪随机数序列初始化，令j1（即将取随机数即将取随机数指针指向伪随机数序列中的第指针指向伪随机数序列中的第1个随机数）。个随机数）。3)检查表

36、中第检查表中第i项的内容：项的内容： 若第若第i项登记着关键字项登记着关键字k，则取出该项元素即可；则取出该项元素即可； 若第若第i项空，则表示在项空，则表示在Hash表中没有该关键字信表中没有该关键字信息；息； 若第若第i项不空，且登记的不是关键字项不空，且登记的不是关键字k，则令则令imod(i0RN(j)，n)，并令并令jj1（即将取随即将取随机数指针指向下一个随机数），转机数指针指向下一个随机数），转3)继续检查。继续检查。 其中其中RN(j)表示伪随机数序列表示伪随机数序列RN中的第中的第j个随机数个随机数。前两种前两种Hash表的缺点表的缺点 在在Hash表填入过程中表填入过程中不

37、顾后效不顾后效，从而在填入过，从而在填入过程中其冲突的机会在不断增多；程中其冲突的机会在不断增多； 当当Hash表表填满填满时，不能正常地进行查找。时，不能正常地进行查找。 解决方法解决方法：将冲突的元素安排在另外的空间内，将冲突的元素安排在另外的空间内，而不占用而不占用Hash表本身的空间，则就不会产生新表本身的空间，则就不会产生新的冲突。的冲突。3. 溢出溢出Hash表表 溢出溢出Hash表包括表包括Hash表表和和溢出表溢出表两部分。两部分。 在在Hash表的填入过程中，将冲突的元素表的填入过程中，将冲突的元素顺序填顺序填入入溢出表，而当查找过程中发现冲突时，就在溢出表，而当查找过程中发

38、现冲突时，就在溢出表中进行顺序查找。溢出表中进行顺序查找。 溢出表是一个溢出表是一个顺序查找表顺序查找表。溢出溢出Hash表的填入表的填入 将关键字将关键字k及有关信息填入溢出及有关信息填入溢出Hash表的步骤表的步骤如下：如下：1)计算关键字计算关键字k的的Hash码码ii(k)。2)检查表中第检查表中第i项的内容：项的内容：若第若第i项为空，则将关键字项为空，则将关键字k及有关信息填入该及有关信息填入该项；项；若第若第i项不空，则将关键字项不空，则将关键字k及有关信息依次填及有关信息依次填入溢出表中的入溢出表中的自由项自由项。溢出溢出Hash表的取出表的取出 要在溢出要在溢出Hash表中取

39、出关键字表中取出关键字k的元素，其步骤的元素，其步骤如下：如下：1)计算关键字计算关键字k的的Hash码码ii(k)。2)检查表中第检查表中第i项的内容：项的内容：若第若第i项登记着关键字项登记着关键字k，则取出该项元素即可；则取出该项元素即可；若第若第i项为空，则表示在项为空，则表示在Hash表中没有该关键字表中没有该关键字信息；信息；若第若第i项不空，且登记的不是关键字项不空，且登记的不是关键字k，则转入在则转入在溢出表中进行溢出表中进行顺序查找顺序查找。 例例3.5 将关键字序列将关键字序列(09，31，26，19，01，13，02，11，27，16，05，21)依次填入长度为依次填入长

40、度为n12的溢出的溢出Hash表中。表中。设设Hash码为码为iINT(k/3)1。表表3.4 Hash表和其溢出表（第表和其溢出表（第173页）页）冲突的元素被填入冲突的元素被填入溢出表的自由项溢出表的自由项3.3 基本排序技术基本排序技术 排序：排序：将一个无序序列整理成将一个无序序列整理成按值非递减顺序按值非递减顺序排列的有序序列。排列的有序序列。 本节所介绍的排序如不做特别说明一般认为是本节所介绍的排序如不做特别说明一般认为是顺序存储的线性表顺序存储的线性表，在程序设计语言中就是一，在程序设计语言中就是一维数组。维数组。3.3.1 冒泡排序与快速排序（互换排序）冒泡排序与快速排序（互换

41、排序） 定义：定义：所谓互换排序是指借助数据元素之间的所谓互换排序是指借助数据元素之间的互换进行排序的一种方法。互换进行排序的一种方法。 冒泡排序（冒泡排序（Bubble Sort）是一种最简单的互换是一种最简单的互换排序，它是通过相邻两项目的比较，按一定次排序，它是通过相邻两项目的比较，按一定次序互换，使表格逐步达到有序化。序互换，使表格逐步达到有序化。 快速排序（快速排序（Quick Sort）是对冒泡排序的一种是对冒泡排序的一种改进。改进。1. 冒泡排序冒泡排序 基本思想：基本思想： 首先对具有首先对具有n个项目的无序表进行扫描，比较相个项目的无序表进行扫描，比较相邻两个元素的大小，若发

42、现邻两个元素的大小，若发现逆序逆序则进行互换，则进行互换，由此可以使由此可以使n个项目中的最大者沉到表的最后；个项目中的最大者沉到表的最后； 然后对剩下的未排序好的项目再进行扫描，使然后对剩下的未排序好的项目再进行扫描，使它们之中的最大者又沉到表的最后；它们之中的最大者又沉到表的最后； 以此类推，直到将表全部排序好为止。以此类推，直到将表全部排序好为止。说明说明：如果每次扫描都将未排序序列中的最大元素沉如果每次扫描都将未排序序列中的最大元素沉到表尾，则排序过程称为单向冒泡排序。如果每次不到表尾，则排序过程称为单向冒泡排序。如果每次不仅向后扫描，而且同时向前扫描，将未排序序列中的仅向后扫描，而且

43、同时向前扫描，将未排序序列中的最小元素浮到表头，则排序过程称为双向冒泡排序。最小元素浮到表头，则排序过程称为双向冒泡排序。大数在前，小大数在前，小数在后！数在后！首先，从表头开始往后扫描线性表，在扫描过程中逐次首先，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元比较相邻两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，称之为素大于后面的元素，则将它们互换，称之为消去了一个逆消去了一个逆序序。显然，在扫描过程中，不断地将两相邻元素中的大者。显然，在扫描过程中，不断地将两相邻元素中的大者往后移动，最后就将往后移动，最后就将线性表

44、中的最大者换到了表的最后线性表中的最大者换到了表的最后。然后从后到前扫描剩下的线性表，同样，在扫描过程中然后从后到前扫描剩下的线性表，同样，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，后面逐次比较相邻两个元素的大小。若相邻两个元素中，后面的元素小于前面的元素，则将它们互换，这样就的元素小于前面的元素，则将它们互换，这样就又消去了又消去了一个逆序一个逆序。显然，在扫描过程中，不断地将两相邻元素中。显然，在扫描过程中，不断地将两相邻元素中的小者往前移动，的小者往前移动，最后就将剩下线性表中的最小者换到了最后就将剩下线性表中的最小者换到了表的最前面表的最前面。对剩下的线性表重复上述过程

45、，直到剩下的线性表变空对剩下的线性表重复上述过程，直到剩下的线性表变空为止，此时的线性表已经变为有序。为止，此时的线性表已经变为有序。（升序）（升序）图图3.3 冒泡排序过程示意图（第冒泡排序过程示意图（第184页）页）2. 快速排序快速排序 在冒泡排序中，每经过一次数据元素的互换只能在冒泡排序中，每经过一次数据元素的互换只能移掉一个逆序。移掉一个逆序。 如果在排序过程中，每经过一次比较，使如果在排序过程中，每经过一次比较，使元素移元素移动不止一个位置动不止一个位置，这就有可能同时移掉多个逆序，这就有可能同时移掉多个逆序，达到加速排序的目的。达到加速排序的目的。 基本思想：基本思想：通过一趟分

46、割将线性表分成两部分，通过一趟分割将线性表分成两部分，其中前一部分的所有元素值其中前一部分的所有元素值均不大于均不大于后一部分中后一部分中的每一个元素值；然后对每一部分在进行分割，的每一个元素值；然后对每一部分在进行分割，直到整个线性表有序为止。直到整个线性表有序为止。具体做法具体做法 从线性表中选取一个元素，设为从线性表中选取一个元素，设为T。然后将线性然后将线性表表后面小于后面小于T的元素移到前面的元素移到前面，而，而前面大于前面大于T的元的元素移动到后面素移动到后面，结果就将线性表分成了两部分，结果就将线性表分成了两部分（两个子表），而（两个子表），而T插入到其分界线的位置处。插入到其分

47、界线的位置处。该过程被称为该过程被称为线性表的分割线性表的分割。 如果对分割后的各子表再按上述原则进行分割，如果对分割后的各子表再按上述原则进行分割，并且这种分割过程可以一直做下去，直到所有子并且这种分割过程可以一直做下去，直到所有子表为空为止，则此时的线性表就变成了表为空为止，则此时的线性表就变成了有序表有序表。 通过一趟分割将线性表分成两部分，其中前一部通过一趟分割将线性表分成两部分，其中前一部分的所有元素值分的所有元素值均不大于均不大于后一部分中的每一个元后一部分中的每一个元素值；素值；快速分割示意图快速分割示意图 首先，在表的首先，在表的第一个第一个、中间一个中间一个与与最后一个最后一

48、个元素中元素中选取选取中项中项，设为，设为L(k)，并将并将L(k)赋给赋给T，再将表中再将表中的第一个元素移到的第一个元素移到L(k)的位置上。的位置上。 然后设置两个指针然后设置两个指针i和和j分别指向表的起始与最后的分别指向表的起始与最后的位置。反复作以下两步：位置。反复作以下两步：(1)将将j逐渐减小，并逐次比较逐渐减小，并逐次比较L(j)与与T，直到发现一直到发现一个个L(j)T为止，为止，将将L(j)移到移到L(i)的位置上的位置上。(2)将将i逐渐增大，并逐次比较逐渐增大，并逐次比较L(i)与与T，直到发现一直到发现一个个L(i)T为止，为止，将将L(i)移到移到L(j)的位置上

49、的位置上。 上述两个操作交替进行，直到指针上述两个操作交替进行，直到指针i与与j指向同一个指向同一个位置（即位置（即ij）为止，此时将为止，此时将T移到移到L(i)的位置上。的位置上。快速排序的过程快速排序的过程初始关键字初始关键字kij一次交换一次交换ij二次交换二次交换ij三次交换三次交换ij四次交换四次交换ij完成一趟排序完成一趟排序ij3.3.2 简单插入排序与希尔排序简单插入排序与希尔排序1. 简单插入排序简单插入排序 基本思想：基本思想：依次将线性表中的每一个元素插入到一依次将线性表中的每一个元素插入到一个已经有序的子表中。个已经有序的子表中。 方法：方法： 将线性表中，将线性表中

50、，只包含第只包含第1个元素的子表个元素的子表显然可以显然可以看成是有序表；看成是有序表； 从线性表的从线性表的第第2个元素开始直到最后一个元素个元素开始直到最后一个元素，逐次将其中的每一个元素插入到前面已经有序的逐次将其中的每一个元素插入到前面已经有序的子表中；子表中； 一般来说，假设线性表中前一般来说，假设线性表中前j-1个元素已经有序，个元素已经有序，现在要现在要将线性表中第将线性表中第j个元素插入到前面的有序子个元素插入到前面的有序子表表中。中。5 5 1 7 3 1 6 9 4 2 8 6 1 7 3 1 6 9 4 2 8 6 j j2 21 1 5 5 7 3 1 6 9 4 2

51、8 6 7 3 1 6 9 4 2 8 6 j j3 31 5 1 5 7 7 3 1 6 9 4 2 8 6 3 1 6 9 4 2 8 6 j j4 41 1 3 3 5 7 5 7 1 6 9 4 2 8 6 1 6 9 4 2 8 6 j j5 51 1 1 1 3 5 7 3 5 7 6 9 4 2 8 6 6 9 4 2 8 6 j j6 6红色的部分红色的部分：有序子表；：有序子表；绿色的部分绿色的部分：之前插入的数字：之前插入的数字1 1 3 5 1 1 3 5 6 6 7 7 9 4 2 8 6 9 4 2 8 6 j j7 71 1 3 5 6 7 1 1 3 5 6 7

52、9 9 4 2 8 6 4 2 8 6 j j8 81 1 3 1 1 3 4 4 5 6 7 9 5 6 7 9 2 8 6 2 8 6 j j9 91 1 1 1 2 2 3 4 5 6 7 9 3 4 5 6 7 9 8 6 8 6 j j10101 1 2 3 4 5 6 7 1 1 2 3 4 5 6 7 8 8 9 9 6 6 j j11111 1 2 3 4 5 6 1 1 2 3 4 5 6 6 6 7 8 9 7 8 9红色的部分红色的部分：有序子表；：有序子表；绿色的部分绿色的部分：之前插入的数字：之前插入的数字#include using namespace std;te

53、mplate void insort( T p , int n ) int j, k; T t; for ( j=1; j=0 )&( pkt ) ) pk+1 = pk; k = k 1; pk+1 = t; return; 数组数组p，存放着待排序列存放着待排序列数组数组p的长度，即待排的长度，即待排序序列中元素的个数序序列中元素的个数简单插入排序简单插入排序当前待排序列（从当前待排序列（从pj到到pn-1）中第中第一个元素的值赋给一个元素的值赋给t将待排序列中第一个元将待排序列中第一个元素素t插入到已排序序列中插入到已排序序列中的合适位置，同时保证的合适位置，同时保证已排序序列仍旧为升序

54、已排序序列仍旧为升序序列序列2. 希尔排序希尔排序 直接插入排序的时间复杂度为直接插入排序的时间复杂度为O(n2)，但是若但是若待排记录序列为待排记录序列为“正序正序”时，其时间复杂度可时，其时间复杂度可以提高至以提高至O(n)。 由此可以设想：由此可以设想： 若待排记录序列按关键字若待排记录序列按关键字“基本有序基本有序”，直，直接插入排序的效率就可大大提高；接插入排序的效率就可大大提高； 一方面，由于直接插入排序算法简单，则在一方面，由于直接插入排序算法简单，则在n值很小时效率也比较高。值很小时效率也比较高。 希尔排序的希尔排序的基本思想基本思想：先将整个待排记录序列分割先将整个待排记录序

55、列分割成为成为若干个子序列分别进行直接插入排序若干个子序列分别进行直接插入排序，待整个，待整个序列中的记录序列中的记录“基本有序基本有序”时，再对全体记录进行时，再对全体记录进行一次直接插入排序。一次直接插入排序。 子序列的分割方法如下：子序列的分割方法如下： 将将物理位置上物理位置上相隔某个增量相隔某个增量h的元素构成一个子的元素构成一个子序列。序列。 在排序过程中，逐次减小这个增量，最后当在排序过程中，逐次减小这个增量，最后当h减减到到1时，进行一次插入排序，排序就完成。时，进行一次插入排序，排序就完成。 增量序列一般取增量序列一般取 htn/2k(k1，2，log2n)，其中其中n为待排

56、序序列的长度。为待排序序列的长度。图图3.6 希尔排序示意图（第希尔排序示意图（第191页）页）希尔排序的希尔排序的C+描述描述 #include using namespace std; template void shel(T p, int n) int k,j,i; T t; k=n/2; while (k0) for (j=k; j=0)&(pit) pi+k=pi; i=i-k; pi+k=t; k=k/2; return;3.3.3 简单选择排序与堆排序简单选择排序与堆排序1. 简单选择排序简单选择排序 基本思想：基本思想：扫描整个线性表，从中选出最小的扫描整个线性表，从中选出最小

57、的元素，将它交换到表的最前面；然后对剩下的元素，将它交换到表的最前面；然后对剩下的子表采用同样的方法，直到子表空为止。子表采用同样的方法，直到子表空为止。 简单选择排序在最坏情况下需要比较：简单选择排序在最坏情况下需要比较：2/ )1( nn图图3.7 简单选择排序例（第简单选择排序例（第192页）页）2. 堆排序堆排序 堆的定义：堆的定义：具有具有n个数据元素的序列（个数据元素的序列（h1, h2, , hn），），当且仅当满足：当且仅当满足： 122iiiihhhh 122iiiihhhh知识回顾知识回顾：如将一棵有如将一棵有n个结点的个结点的完全二叉树完全二叉树自顶向下，自顶向下，同一层

58、自左向右连续给结点编号同一层自左向右连续给结点编号 1, 2, , n，则有以下则有以下关系：若关系：若i = 1, 则则i无双亲；若无双亲；若i 1, 则则i的双亲为的双亲为i /2；若若2i n, 则则i无左孩子；否则，无左孩子；否则，i的左孩子为的左孩子为2i；若若2i+1 n, 则则i无右孩子；否则，无右孩子；否则，i的右孩子为的右孩子为2i+1。完全二叉树完全二叉树 顺序表示顺序表示hi h2i &hi h2i+1完全二叉树完全二叉树 顺序表示顺序表示hi h2i &hi h2i+1098778456531235317098778456531532317 09 17 65 23 45

59、 78 87 53 31 87 78 53 45 65 09 31 17 23 1 2 3 4 5 6 7 8 9对应的对应的数组：数组：小根堆小根堆大根堆大根堆举例举例 序列序列(91，85，53，36，47，30，24，12)是一个堆：是一个堆：图图3.8 堆顶元素为最大项（第堆顶元素为最大项（第194页）页）如果用完全二叉树表示堆，则树中所有非叶子结点值如果用完全二叉树表示堆，则树中所有非叶子结点值均不小于其左、右子树的根结点值。因此均不小于其左、右子树的根结点值。因此堆顶（完全堆顶（完全二叉树的根）元素必为序列中二叉树的根）元素必为序列中n个元素的最大值个元素的最大值。堆排序的方法：堆

60、排序的方法：首先输出堆顶元素（当前待排序列的最大值）；首先输出堆顶元素（当前待排序列的最大值）；然后将剩下的然后将剩下的n-1个元素再调整为堆，其堆顶元素个元素再调整为堆，其堆顶元素为次大项，再将它输出；为次大项，再将它输出；反复这个过程，直到堆空为止。此时，输出序列反复这个过程，直到堆空为止。此时，输出序列的的逆序逆序即为有序序列。即为有序序列。堆排序的关键问题：堆排序的关键问题：如何由无序序列建堆；（如何由无序序列建堆；（堆构造问题堆构造问题）1. 在输出堆顶元素之后，如何将剩余元素重新调整在输出堆顶元素之后，如何将剩余元素重新调整为堆。（为堆。（调整建堆调整建堆） 调整建堆调整建堆 在具