计算机软件技术05第三章查找与排序技术(上)40学时.ppt

第三章 查找与排序技术 Date1计算机软件技术基础 第三章 查找与排序技术（上 ） 第三章 查找与排序技术 3.1 基本查找技术 查找：在一个给定的数据结构中查找某个指定 的元素。 通常，根据不同的数据结构，应该采用不同的 查找方法： 顺序查找； 有序表的对分查找； 分块查找。 Date2计算机软件技术基础 第三章 查找与排序技术（上 ） 3.1.1 顺序查找 顺序查找（顺序搜索）：在线性表中查找指定 的元素。 顺序查找的基本方法：从线性表的第一个元素 开始，依次将线性表中的元素与被查元素进行 比较，若相等则表示找到（查找成功）；若线 性表中的所有元素都与被查元素进行了比较但 都不相等，则表示线性表中没有要找到的元素 （查找失败）。 Date3计算机软件技术基础 第三章 查找与排序技术（上 ） 回顾：举例说明 举例：设L是 包含n个元素 的一维数组。 对于指定的输 入x，如果x在 数组中，则顺 序找到它第一 次出现处的下 标； 如果x不在 数组中，则 以下标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。 Date4计算机软件技术基础 第三章 查找与排序技术（上 ） 回顾：平均性态分析 设被查项x在数组L中的概率为q。当输入的x为 L(i)时，算法所做的比较次数为： 再假设输入的x出现在数组中的每个位置上的 可能性是一样的，即 其中x=L(n+1)表示x不在数组L中的情况。 Date5计算机软件技术基础 第三章 查找与排序技术（上 ） 顺序查找的效率 如果线性表中的第一个元素就是被查找元素 ，只需要做一次比较就查找成功； 如果被查的元素是线性表中的最后一个元素 ，或者被查元素根本不在线性表中，则需要 与线性表中的所有元素进行比较（最坏情况 ）； 平均情况：利用顺序查找法在线性表中查找 一个元素，大约要与线性表中一半的元素进 行比较。 Date6计算机软件技术基础 第三章 查找与排序技术（上 ） 结论 对于大的线性表来说，顺序查找的效率是很 低的。但在下列两种情况下也只能采用顺序 查找： 如果线性表为无序表（表中元素的排列是无 序的），则不管是顺序存储结构还是链式存 储结构，都只能用顺序查找表； 即使是有序线性表，如果采用链式存储结构 ，也只能用顺序查找。 Date7计算机软件技术基础 第三章 查找与排序技术（上 ） 3.1.2 有序表的对分查找 有序表：线性表中的元素按值非递减或者非递增 排列。 对分查找的过程：将被查找关键字与线性表中间 的项目进行比较，有三种可能： 若被查关键字与表中间的项目相等，则查到，过 程结束； 若被查关键字大于表中间的项目，则取表的后半 部分作为新表再去查找； 若被查关键字小于表中间的项目，则取表的前半 部分作为新表再去查找。 升序降序 查找成功！ 在后半部分查找 ！ 在前半部分查找 ！ 减半递推！ Date8计算机软件技术基础 第三章 查找与排序技术（上 ） 时间效率分析 对分查找是根据每次试探的结果将线性表的 规模减半，并有规则地括出可能包含被查项 目的部分。 最坏情况：对查找需要的比较次数为 n为线性表的长度。 局限性：只适用于有序表，且只限于顺序存 储结构。 Date9计算机软件技术基础 第三章 查找与排序技术（上 ） #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); /顺序有序表查找 顺序有序表的长度 顺序有序表的对分查找 Date10计算机软件技术基础 第三章 查找与排序技术（上 ） /顺序有序表查找 template int SL_List:search_SL_List( 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个元素结束 。 Date11计算机软件技术基础 第三章 查找与排序技术（上 ） 3.1.3 分块查找 分块查找又称索引查找，是顺序查找的一种 改进方法，用于在“分块有序”表中进行查找 。 “分块有序”表：将长度为n线性表L分成m个 子表（各子表的长度可以不等，也可以相等 ），且后一个子表中的每一项均大于前一个 子表中的所有项。 Date12计算机软件技术基础 第三章 查找与排序技术（上 ） 分块有序表 分块有序表的结构可以分为两部分： (1)线性表本身采用顺序存储结构也可以采用链 式存储结构。 (2)再建立一个索引表。在索引表中，对线性表 的每个子表建立一个索引结点，每个结点包括 两个域：一是数据域，用于存放对应子表中的 最大元素值；二是指针域，用于指示对应子表 的第一个元素在整个线性表中的序号或者地址 。 Date13计算机软件技术基础 第三章 查找与排序技术（上 ） 图3.1 分块有序表例（第161页） 长度为n线性表L分成m个子表，各子表的长 度可以不等，也可以相等； 后一个子表中的每一项均大于前一个子表中 的所有项。 Date14计算机软件技术基础 第三章 查找与排序技术（上 ） 图3.1 分块有序表例（第161页） 线性表本身采用顺序存储结构。 再建立一个索引表。在索引表中，对线性表的每个 子表建立一个索引结点，每个结点包括两个域：一 是数据域，用于存放对应子表中的最大元素值；二 是指针域，用于指示对应子表的第一个元素在整个 线性表中的序号。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Date15计算机软件技术基础 第三章 查找与排序技术（上 ） 分析 根据分块有序表的结构，其查找过程可以分以 下两步进行： (1)首先查找索引表，以便确定被查元素所在的 子表。由于索引表数据域中的数据是有序的且 顺序存储，因此可以采用对分查找。 (2)然后在相应的子表中用顺序查找法进行具体 的查找。 结论：分块查找的效率介于对分查找和顺序查 找之间。 Date16计算机软件技术基础 第三章 查找与排序技术（上 ） 3.2 哈希表技术 在前面所介绍的各种查找方法中，均通过将 关键字与表中的各项目直接进行比较而达到 查找的目的。 Hash表是另一种查找技术：对被查关键字作 某种运算后直接确定所要查找项目在表中的 位置。 Date17计算机软件技术基础 第三章 查找与排序技术（上 ） 3.2.1 哈希表的基本概念 1. 直接查找技术 设表的长度为n。如果存在一个函数ii(k)， 对于表中的任意一个元素的关键字k，满足以 下条件： (1)函数值i的范围为：1in； (2)对于任意的元素关键字k1k2，恒存在 i(k1)i(k2)。 则称此表为直接查找表。 其中函数ii(k)称为关键字k的映象函数。 Date18计算机软件技术基础 第三章 查找与排序技术（上 ） 直接查找技术 直接查找表中各元素的关键字k与表项序号i之 间存在着一一对应的关系； 对直接查找表的查找，只需要根据映像函数 i=i(k)计算出待查关键字项目在表中的序号i即 可。 Date19计算机软件技术基础 第三章 查找与排序技术（上 ） 2. Hash表 Hash表技术是直接查找技术的推广，其主要目 标是提高查找效率。 直接查找技术要求映像函数能使得表中任意两 个不同的关键字其映像函数值也不同（不允许 元素冲突的存在）；但在实际应用中，这一条 件很难满足。 对于两个不同的关键字k1 k2有i(k1)=i(k2)，发生 了元素冲突，即两个不同元素需要存在在同一 个存储单元中。 Date20计算机软件技术基础 第三章 查找与排序技术（上 ） 举例 例3.2 将关键字序列(09，31，26，19，01，13 ，02，11，27，16，05，21)依次填入长度为n 12的表中。映象函数为iINT(k/3)1。 关键字01和02发生冲突 ：因为两个数值都想要 存放在表的第1项中。 关键字09和11发生冲突 ：因为两个数值都想要 存放在表的第4项中。 Date21计算机软件技术基础 第三章 查找与排序技术（上 ） 分析 显然，当有元素发生冲突时，是无法进行直接 查找的。所以引入Hash表的概念： 设表的长度为n。若存在一个映象函数i=i(k) ，对于表中任一元素的关键字k，满足1 i(k) n ，则称此表为Hash表。并称i(k)为关 键字k的Hash码。 Hash表中允许的冲突存在。如果在Hash表 中没有冲突存在，则Hash表就成为直接查 找表。 Date22计算机软件技术基础 第三章 查找与排序技术（上 ） 处理表中元素的主要工作： (1)构造合适的Hash码，以便尽量减少表中元素冲 突的次数。 (2)当表中元素发生冲突时，要进行适当的处理。 3. Hash码的构造 查找关键字为k的元素时，计算Hash码i(k)的工作量 是影响效率的重要因素。 在实际构造Hash码时，要考虑如下两方面的因素： (1)使各关键字尽可能均匀地分布在Hash表中，即 Hash码的均匀性要好，以便减少冲突发生的机会。 (2)Hash码的计算要尽量简单。 Date23计算机软件技术基础 第三章 查找与排序技术（上 ） 一些简单的Hash码构造方法 截段法 分段叠加法 除法 乘法 Date24计算机软件技术基础 第三章 查找与排序技术（上 ） 截段法 因为关键字是一种基本的符号串，而在计算机中 就是一个经过编码的二进制数字串。 截取法：选取与关键字对应的数字串中的一段（ 一般选取低位数）作为关键字的Hash码。 分段叠加法 将关键字的编码串分割成若干段，然后把它们叠 加后再进行截段。两种叠加处理的方法： 移位叠加：将分割后的几部分低位对齐相加； 间界叠加：从一端沿分割界来回折送，然后对齐 相加。 此法适于关键字的数字位数特别多的情况。 Date25计算机软件技术基础 第三章 查找与排序技术（上 ） 有80个记录，关键字为8位十进制数，哈希地 址为2位十进制数。 8 1 3 4 6 5 3 2 8 1 3 7 2 2 4 2 8 1 3 8 7 4 2 2 8 1 3 0 1 3 6 7 8 1 3 2 2 8 1 7 8 1 3 3 8 9 6 7 8 1 3 6 8 5 3 7 8 1 4 1 9 3 5 5 分析： 只取8 只取1 只取3、4 只取2、7、5 数字分布近乎随机 所以：取任意两位或两位 与另两位的叠加作哈希地址 截段法：选取与关键字对应的数字串中的一段（一 般选取低位数）作为关键字的Hash码。 Date26计算机软件技术基础 第三章 查找与排序技术（上 ） 举例: 关键字为 0442205864，哈希地址位数为4 5 8 6 4 4 2 2 0 0 4 1 0 0 8 8 H(key)=0088 移位叠加 5 8 6 4 0 2 2 4 0 4 6 0 9 2 H(key)=6092 间界叠加 分段叠加法 将关键字的编码串分割成若干段，然后把它们叠加 后再进行截段。两种叠加处理的方法： 1.移位叠加：将分割后的几部分低位对齐相加； 2.间界叠加：从一端沿分割界来回折送，然后对齐相 加。 Date27计算机软件技术基础 第三章 查找与排序技术（上 ） 除法 imod(k，n) 其中k为关键字，n为Hash表的长度，而mod 为模余运算符； 当mod(k，n)=0时，取i=n（本节规定）。 乘法 imod(k*，n) 一般取0.618033988747，或0.6125423371，或 0.6161616161。 Date28计算机软件技术基础 第三章 查找与排序技术（上 ） 3.2.2 几种常用的Hash表 1. 线性Hash表 线性表是一种最简单的Hash表。 设线性Hash表的长度为m，则对线性Hash表 的查找过程如下： Date29计算机软件技术基础 第三章 查找与排序技术（上 ） 线性Hash表的填入 将关键字k及有关信息填入线性Hash表的步骤 如下： 1)计算关键字k的Hash码ii(k)。 2)检查表中第i项的内容： 若第i项为空，则将关键字k及有关信息填入 该项； 若第i项不空，则令imod(i1，n)，转2)继 续检查。 只要Hash表尚未填满，最终总可以找到一个空 项，将关键字k及有关信息填入到Hash表中。 线性Hash表的 冲突处理。 Date30计算机软件技术基础 第三章 查找与排序技术（上 ） 线性Hash表的取出 要在线性Hash表中取出关键字k的元素，其步骤 如下： 1)计算关键字k的Hash码ii(k)。 2)检查表中第i项的内容： 若第i项登记着关键字k，则取出该项元素即 可； 若第i项为空，则表示在Hash表中没有该关键 字的信息； 若第i项不空，且登记的不是关键字k，则令i mod(i1，n)转2)继续检查。 Date31计算机软件技术基础 第三章 查找与排序技术（上 ） 例3.3 将关键字序列(09，31，26，19，01，13， 02，11，27，16，05，21)依次填入长度为n12 的线性Hash表中。 设Hash码为iINT(k/3)1。 表3.2 线性Hash表（第164页） Date32计算机软件技术基础 第三章 查找与排序技术（上 ） 分析 线性表的优点：简单。 线性Hash表的缺点： 在线性Hash表填入的过程中，当发生冲突时，首 先考虑的是下一项，因此，当Hash码的冲突较多 时，在线性Hash表中会存在“堆聚”现象，即许多 关键字被连续登记在一起，从而会降低查找效率 。 在线性Hash表的填入过程中，处理冲突时会带来 新的冲突。线性Hash表的填入方法是不顾后效的 。 Date33计算机软件技术基础 第三章 查找与排序技术（上 ） n为Hash表的长度，而m为Hash表中实际存在 的关键字个数。 注意：Hash表的平均查找次数E不依赖于表的 长度，而只与表的填满率有关。 此公式只仅在知 道表长n和实际填 放关键字个数m的 情况下有效！ 如果有一个确定 Hash表，则要确定 表的平均查找次数 就必须要采用平均 性态法求取！ Date34计算机软件技术基础 第三章 查找与排序技术（上 ） 2. 随机Hash表 当Hash表的长度n为2的乘幂时（n=2k），可 以定义另一种Hash表随机Hash表。 随机Hash表与线性Hash表的不同之处在于： 一旦发生元素冲突时，表项序号i的改变不是 采用加1取模的方法，而是用某种伪随机数来 改变i值。 Date35计算机软件技术基础 第三章 查找与排序技术（上 ） 随机Hash表的填入 将关键字k及有关信息填入随机Hash表的步骤如下 ： 1)计算关键字k的Hash码i0i(k)。且令ii0。 2)伪随机数序列初始化，令j1（即将取随机数指针 指向伪随机数序列中的第1个随机数）。 3)检查表中第i项的内容： 若第i项为空，则将关键字k及有关信息填入该 项； 若第i项不空，则令imod(i0RN(j)，n)，并令 jj1（即将取随机数指针指向下一个随机数 ），转3)继续检查。 其中RN(j)表示伪随机数序列RN中的第j个随机数 。 Date36计算机软件技术基础 第三章 查找与排序技术（上 ） 伪随机数的产生 伪随机数序列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表的表长 求模取余 取整 Date37计算机软件技术基础 第三章 查找与排序技术（上 ） 例3.4 将关键字序列(09，31，26，19，01，13， 02，11，27，16，05，21)依次填入长度为n24 16的随机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页） Date38计算机软件技术基础 第三章 查找与排序技术（上 ） 随机Hash表的取出 要在随机Hash表中取出关键字k的元素，其步 骤如下： 1)计算关键字k的Hash码i0i(k)。且令ii0。 2)伪随机数序列初始化，令j1（即将取随机数 指针指向伪随机数序列中的第1个随机数）。 Date39计算机软件技术基础 第三章 查找与排序技术（上 ） 3)检查表中第i项的内容： 若第i项登记着关键字k，则取出该项元素即可 ； 若第i项空，则表示在Hash表中没有该关键字信 息； 若第i项不空，且登记的不是关键字k，则令 imod(i0RN(j)，n)，并令jj1（即将取随 机数指针指向下一个随机数），转3)继续检查 。 其中RN(j)表示伪随机数序列RN中的第j个随机数 。 Date40计算机软件技术基础 第三章 查找与排序技术（上 ） 前两种Hash表的缺点 在Hash表填入过程中不顾后效，从而在填入 过程中其冲突的机会在不断增多； 当Hash表填满时，不能正常地进行查找。 解决方法：将冲突的元素安排在另外的空间 内，而不占用Hash表本身的空间，则就不会 产生新的冲突。 Date41计算机软件技术基础 第三章 查找与排序技术（上 ） 3. 溢出Hash表 溢出Hash表包括Hash表和溢出表两部分。 在Hash表的填入过程中，将冲突的元素顺序 填入溢出表，而当查找过程中发现冲突时， 就在溢出表中进行顺序查找。 溢出表是一个顺序查找表。 Date42计算机软件技术基础 第三章 查找与排序技术（上 ） 溢出Hash表的填入 将关键字k及有关信息填入溢出Hash表的步骤 如下： 1)计算关键字k的Hash码ii(k)。 2)检查表中第i项的内容： 若第i项为空，则将关键字k及有关信息填入该 项； 若第i项不空，则将关键字k及有关信息依次填 入溢出表中的自由项。 Date43计算机软件技术基础 第三章 查找与排序技术（上 ） 溢出Hash表的取出 要在溢出Hash表中取出关键字k的元素，其步 骤如下： 1)计算关键字k的Hash码ii(k)。 2)检查表中第i项的内容： 若第i项登记着关键字k，则取出该项元素即可 ； 若第i项为空，则表示在Hash表中没有该关键 字 信息； 若第i项不空，且登记的不是关键字k，则转入 在溢出表中进行顺序查找。 Date44计算机软件技术基础 第三章 查找与排序技术（上 ） 例3.5 将关键字序列(09，31，26，19，01，13 ，02，11，27，16，05，21)依次填入长度为n 12的溢出Hash表中。 设Hash码为iINT(k/3)1。 表3.4 Hash表和其溢出表（第173页） 冲突的元素被填入 溢出表的自由项 Date45计算机软件技术基础 第三章 查找与排序技术（上 ） 3.3 基本排序技术 排序：将一个无序序列整理成按值非递减顺 序排列的有序序列。 本节所介绍的排序如不做特别说明一般认为 是顺序存储的线性表，在程序设计语言中就 是一维数组。 Date46计算机软件技术基础 第三章 查找与排序技术（上 ） 3.3.1 冒泡排序与快速排序（互换排序） 定义：所谓互换排序是指借助数据元素之间 的互换进行排序的一种方法。 冒泡排序（Bubble Sort）是一种最简单的互 换排序，它是通过相邻两项目的比较，按一 定次序互换，使表格逐步达到有序化。 快速排序（Quick Sort）是对冒泡排序的一种 改进。 Date47计算机软件技术基础 第三章 查找与排序技术（上 ） 1. 冒泡排序 基本思想： 首先对具有n个项目的无序表进行扫描，比较 相邻两个元素的大小，若发现逆序则进行互换 ，由此可以使n个项目中的最大者沉到表的最 后； 然后对剩下的未排序好的项目再进行扫描，使 它们之中的最大者又沉到表的最后； 以此类推，直到将表全部排序好为止。 说明：如果每次扫描都将未排序序列中的最大元素沉 到表尾，则排序过程称为单向冒泡排序。如果每次不 仅向后扫描，而且同时向前扫描，将未排序序列中的 最小元素浮到表头，则排序过程称为双向冒泡排序。 大数在前，小 数在后！ Date48计算机软件技术基础 第三章 查找与排序技术（上 ） 首先，从表头开始往后扫描线性表，在扫描过程中逐 次比较相邻两个元素的大小。若相邻两个元素中，前面 的元素大于后面的元素，则将它们互换，称之为消去了 一个逆序。显然，在扫描过程中，不断地将两相邻元素 中的大者往后移动，最后就将线性表中的最大者换到了 表的最后。 然后从后到前扫描剩下的线性表，同样，在扫描过程 中逐次比较相邻两个元素的大小。若相邻两个元素中， 后面的元素小于前面的元素，则将它们互换，这样就又 消去了一个逆序。显然，在扫描过程中，不断地将两相 邻元素中的小者往前移动，最后就将剩下线性表中的最 小者换到了表的最前面。 对剩下的线性表重复上述过程，直到剩下的线性表变 空为止，此时的线性表已经变为有序。（升序） Date49计算机软件技术基础 第三章 查找与排序技术（上 ） 图3.3 冒泡排序过程示意图（第184页） Date50计算机软件技术基础 第三章 查找与排序技术（上 ） 2. 快速排序 在冒泡排序中，每经过一次数据元素的互换只 能移掉一个逆序。 如果在排序过程中，每经过一次比较，使元素 移动不止一个位置，这就有可能同时移掉多个 逆序，达到加速排序的目的。 基本思想：通过一趟分割将线性表分成两部分 ，其中前一部分的所有元素值均不大于后一部 分中的每一个元素值；然后对每一部分再进行 分割，直到整个线性表有序为止。 Date51计算机软件技术基础 第三章 查找与排序技术（上 ） 具体做法 从线性表中选取一个元素，设为T。然后将线性 表后面小于T的元素移到前面，而前面大于T的 元素移动到后面，结果就将线性表分成了两部 分（两个子表），而T插入到其分界线的位置处 。该过程被称为线性表的分割。 如果对分割后的各子表再按上述原则进行分割 ，并且这种分割过程可以一直做下去，直到所 有子表为空为止，则此时的线性表就变成了有 序表。 Date52计算机软件技术基础 第三章 查找与排序技术（上 ） 通过一趟分割将线性表分成两部分，其中前一部 分的所有元素值均不大于后一部分中的每一个元 素值； 从线性表中选取一个元素，设为T。然后将线 性表后面小于T的元素移到前面，而前面大于 T的元素移动到后面; 而T插入到其分界线的位置处。该过程被称为 线性表的分割。 快速分割示意图 Date53计算机软件技术基础 第三章 查找与排序技术（上 ） 首先，在表的第一个、中间一个与最后一个元素 中选取中项，设为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)的位置上。 上述两个操作交替进行，直到指针i与j指向同一个 位置（即ij）为止，此时将T移到L(i)的位置上 。 Date54计算机软件技术基础 第三章 查找与排序技术（上 ） 快速排序的过程 212108082525494925*25*1616 初始关键字 k i j 08082525494925*25*16162121 一次交换 ij 08082525494925*25*16162121二次交换 i j 0808 2525 494925*25*16162121三次交换 ij 08082525494925*25*16162121四次交换 i j 08082525494925*25*16162121完成一趟排序 ij Date55计算机软件技术基础 第三章 查找与排序技术（上 ） 3.3.2 简单插入排序与希尔排序 1. 简单插入排序 基本思想：依次将线性表中的每一个元素插入到一 个已经有序的子表中。 方法： 将线性表中，只包含第1个元素的子表显然可以 看成是有序表； 从线性表的第2个元素开始直到最后一个元素， 逐次将其中的每一个元素插入到前面已经有序 的子表中； 一般来说，假设线性表中前j-1个元素已经有序 ，现在要将线性表中第j个元素插入到前面的有 序子表中。 Date56计算机软件技术基础 第三章 查找与排序技术（上 ） 5 1 7 3 1 6 9 4 2 8 6 j2 1 5 7 3 1 6 9 4 2 8 6 j3 1 5 7 3 1 6 9 4 2 8 6 j4 1 3 5 7 1 6 9 4 2 8 6 j5 1 1 3 5 7 6 9 4 2 8 6 j6 红色的部分：有序子表；绿色的部分：之前插入的数字 Date57计算机软件技术基础 第三章 查找与排序技术（上 ） 1 1 3 5 6 7 9 4 2 8 6 j7 1 1 3 5 6 7 9 4 2 8 6 j8 1 1 3 4 5 6 7 9 2 8 6 j9 1 1 2 3 4 5 6 7 9 8 6 j10 1 1 2 3 4 5 6 7 8 9 6 j 11 1 1 2 3 4 5 6 6 7 8 9 红色的部分：有序子表；绿色的部分：之前插入的数字 Date58计算机软件技术基础 第三章 查找与排序技术（上 ） #include using namespace std; template void insort( T p , int n ) int j, k; T t; for ( j=1; j=0 ) k = k 1; pk+1 = t; return; 数组p，存放着待排序列 数组p的长度，即待排 序序列中元素的个数 简单插入排序 当前待排序列（从 pj到pn-1）中第 一个元素的值赋给t 将待排序列中第一个元 素t插入到已排序序列中 的合适位置，同时保证 已排序序列仍旧为升序 序列Date59计算机软件技术基础 第三章 查找与排序技术（上 ） 2. 希尔排序 直接插入排序的时间复杂度为O(n2)，但是若 待排记录序列为“正序”时，其时间复杂度可 以提高至O(n)。 由此可以设想： 若待排记录序列按关键字“基本有序”，直 接插入排序的效率就可大大提高； 一方面，由于直接插入排序算法简单，则 在n值很小时效率也比较高。 Date60计算机软件技术基础 第三章 查找与排序技术（上 ） 希尔排序的基本思想：先将整个待排记录序列分 割成为若干个子序列分别进行直接插入排序，待 整个序列中的记录“基本有序”时，再对全体记录 进行一次直接插入排序。 子序列的分割方法如下： 将物理位置上相隔某个增量h的元素构成一个子 序列。 在排序过程中，逐次减小这个增量，最后当h减 到1时，进行一次插入排序，排序就完成。 增量序列一般取 htn/2k(k1，2，log2n) ，其中n为待排序序列的长度。 Date61计算机软件技术基础 第三章 查找与排序技术（上 ） 图3.6 希尔排序示意图（第191页） Date62计算机软件技术基础 第三章 查找与排序技术（上 ） 希尔排序的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) i=i-k; pi+k=t; k=k/2; return; Date63计算机软件技术基础 第三章 查找与排序技术（上 ） 3.3.3 简单选择排序与堆排序 1. 简单选择排序 基本思想：扫描整个线性表，从中选出最小的 元素，将它交换到表的最前面；然后对剩下的 子表采用同样的方法，直到子表空为止。 简单选择排序在最坏情况下需要比较： Date64计算机软件技术基础 第三章 查找与排序技术（上 ） 图3.7 简单选择排序例（第192页） Date65计算机软件技术基础 第三章 查找与排序技术（上 ） 2. 堆排序 堆的定义：具有n个数据元素的序列（h1, h2, , hn），当且仅当满足： 大根堆大根堆 小根堆小根堆 知识回顾：如将一棵有n个结点的完全二叉树自顶向下 ，同一层自左向右连续给结点编号 1, 2, , n，则有以 下关系：若i = 1, 则i无双亲；若i 1, 则i的双亲为i /2 ；若2i n, 则i无左孩子；否则，i的左孩子为2i；若 2i+1 n, 则i无右孩子；否则，i的右孩子为2i+1。 Date66计算机软件技术基础 第三章 查找与排序技术（上 ） 完全二叉树 顺序表示 hi h2i & hi h2i+1 完全二叉树 顺序表示 hi h2i & hi h2i+1 09 87 78 456531 23 53 17 09 877845 65 3153 23 17 09 17 65 23 45 78 87 53 31 87 78 53 45 65 09 31 17 23 1 2 3 4 5 6 7 8 9 对应的数 组： 小根堆 大根堆 Date67计算机软件技术基础 第三章 查找与排序技术（上 ） 举例 序列(91，85，53，36，47，30，24，12)是一个堆 ： 图3.8 堆顶元素为最大项（第194页） 如果用完全二叉树表示堆，则树中所有非叶子结点值 均不小于其左、右子树的根结点值。因此堆顶（完全 二叉树的根）元素必为序列中n个元素的最大值。 Date68计算机软件技术基础 第三章 查找与排序技术（上 ） 堆排序的方法： 首先输出堆顶元素（当前待排序列的最大值）； 然后将剩下的n-1个元素再调整为堆，其堆顶元素 为次大项，再将它输出； 反复这个过程，直到堆空为止。此时，输出序列 的逆序即为有序序列。 堆排序的关键问题： 如何由无序序列建堆；（堆构造问题） 在输出堆顶元素之后，如何将剩余元素重新调整 为堆。（调整建堆） Date69计算机软件技术基础 第三章 查找与排序技术（上 ） 调整建堆 在具体讨论无序序列建堆之前，先讨论这样一个 问题：在一棵具有n个结点的完全二叉树（用一 维数组H(1：n)表示）中，假设结点H(m)的左右 子树均为堆，现要将以H(m)为根结点的子树也 调整为堆。 举例：紫色圆圈内的为两个左右子树为堆，但整 个树需要调整。 Date70计算机软件技术基础 第三章 查找与排序技术（上 ） 出现了新的问题，继续调整。 Date71计算机软件技术基础 第三章 查找与排序技术（上 ） 最终的结果，整棵树为一个堆。 Date72计算机软件技术基础 第三章 查找与排序技术（上 ） 分析：调整建堆 调整建堆的基本思想： 总是将根结点值与左、右子树的根结点值进 行比较，若不满足堆的条件，则将左、右子 树根结点值中的大者与根结点值进行交换； 这一调整过程一直做到所有子树均为堆为止 。 Date73计算机软件技术基础 第三章 查找与排序技术（上 ） 构造堆问题 有了调整建堆的算法后，就可以将一个无序 序列建成为堆。 假设无序序列H(1:n)以完全二叉树表示。从完 全二叉树的最后一个非叶子结点（即第n/2个 元素）开始，直到根结点（即第一个元素） 为止，对每一个结点进行调整建堆，最后就 可以得到与该序列对应的堆。 Date74计算机软件技术基础 第三章 查找与排序技术（上 ） 构造堆举例 举例：将以下序列 16，28，17，9，10，11 ，13，22，24，5 构造成堆。 28 2417 2210 1695 1113 假设无序序列H(1:n) 以完全二叉树表示。 从完全二叉树的最后 一个非叶子结点（即 第n/2个元素）开始， 直到根结点（即第一 个元素）为止，对每 一个结点进行调整建 堆，最后就可以得到 与该序列对应的堆。 Date75计算机软件技术基础 第三章 查找与排序技术（上 ） 堆排序算法 首先将一个无序序列建成堆。 然后将堆顶元素（序列中的最大项）与堆中最 后一个元素交换（最大项应该在序列的最后） 。不考虑已经换到最后的那个元素，只考虑前n 1个元素构成的子序列，显然，该子序列已不 是堆，但左、右子树仍为堆，可以将该子序列 调整为堆。 反复做第2步，直到剩下的子序列为空为止。 Date76计算机软件技术基础 第三章 查找与排序技术（上 ） 初始大根堆的建立过程 2121 2525 25*25* 4949 16160808 1 2 3 456 i i 初始排序码集合i = 3 时的局部调整 初始元素序列为：21, 25, 49, 25*, 16, 08 2121 2525 25*25*1616 4949 0808 1 3 654 2 i i Date77计算机软件技术基础 第三章 查找与排序技术（上 ） 2121 2525 25*25* 4949 16160808 1 2 3 456 i i i = 1 时的局部调整 形成最大堆 i = 2 时的局部调整 4949 2525 25*25*1616 2121 0808 0 2 543 1 Date78计算机软件技术基础 第三章 查找与排序技术（上 ） 4949 2525 25*25* 2121 16160808 1 2 3 456 08 25 21 25* 16 4908 25 21 25* 16 49 交换交换 1 1 号与号与 6 6 号对象号对象, , 6 6 号对象就位号对象就位 49 25 21 25* 16 0849 25 21 25* 16 08 初始最大堆初始最大堆 0808 2525 25*25*1616 2121 4949 1 3 654 2 基于初始堆进行堆排序 Date79计算机软件技术基础 第三章 查找与排序技术（上 ） 16 25* 21 08 25 4916 25* 21 08 25 49 交换交换 1 1 号与号与 5 5 号对象号对象, , 5 5 号对象就位号对象就位 25 25* 21 08 16 4925 25* 21 08 16 49 从从 1 1 号到号到 5 5 号号 重新重新 调整为最大堆调整为最大堆 2525 25*25* 0808 2121 16164949 1 2 3 456 1616 25*25* 08082525 2121 4949 1 3 654 2 Date80计算机软件技术基础 第三章 查找与排序技术（上 ） 08 16 21 25* 25 4908 16 21 25* 25 49 交换交换 1 1 号与号与 4 4 号对象号对象, , 4 4 号对象就位号对象就位 25* 16 21 08 25 4925* 16 21 08 25 49 从从 1 1 号到号到 4 4 号号 重新重新 调整为最大堆调整为最大堆 25*25* 1616 0808 2121 25254949 1 2 3 456 0808 1616 25*25*2525 2121 4949 1 3 654 2 Date81计算机软件技术基础 第三章 查找与排序技术（上 ） 08 16 21 25* 25 4908 16 21 25* 25 49 交换交换 1 1 号与号与 3 3 号对象号对象, , 3 3 号对象就位号对象就位 21 16 08 25* 25 4921 16 08 25* 25 49 从从 1 1 号到号到 3 3 号号 重新重新 调整为最大堆调整为最大堆 2121 1616 25*25* 0808 25254949 1 2 3 456 4 0808 1616 25*25*2525 2121 4949 1 3 65 2 Date82计算机软件技术基础 第三章 查找与排序技术（上 ） 08 16 21 25* 25 4908 16 21 25* 25 49 交换交换 1 1 号与号与 2 2 号对象号对象, , 2 2 号对象就位号对象就位 16 08 21 25* 25 4916 08 21 25* 25 49 从从 1 1 号到号到 2 2 号号 重新重新 调整为最大堆调整为最大堆 1616 0808 25*25* 2121 25254949 1 2 3 456 0808 1616 25*25*2525 2121 4949 1 3 654 2 Date83计算机软件技术基础 第三章 查找与排序技术（上 ） 再例 举例：将以下序列 16，28，17，9，10，11 ，13，22，24，5 进行堆排序。 28 2417 2210 1695 1113 Date84计算机软件技术基础 第三章 查找与排序技术（上 ） 分析 堆排序的方法对于规模较小的线性表并不适 宜，但对于较大规模的线性表来说是很有效 的。 堆排序的优点： 在最坏情况下，堆排序的时间复杂度为 在堆排序过程中，在进行元素交换时只需 要一个辅助变量。 Date85计算机软件技术基础 第三章 查找与排序技术（上 ） 3.3.4 其他排序方法简介 1. 归并排序 所谓归并是将两个或两个以上的有序表合并成 一个新的有序表。 考虑一种特殊的归并情况：设线性表L(1：n) 中的某段L(low：high)已经部分有序，即它的 两个子表L(low：mid)与L(mid1：high)（其 中lowmidhigh）已经有序，现要将这两个 有序子表归并成一个有序子表L(low：high)。 Date86计算机软件技术基础 第三章 查找与排序技术（上 ） 实现上述两个子表归并的基本做法如下： (1)开辟一个与线性表L同样大小的表空间A。 (2)设置三个指针i，j，k，其初始状态分别指向两 个有序子表的首部及表空间A中与L中需要进行排 序段相对应空间的首部。即ilow，jmid1， klow。 (3)沿两个有序子表扫描： 若L(i)L(j)，则A(k)L(i)，且i