软件技术基础查找与排序技术

《软件技术基础查找与排序技术》由会员分享，可在线阅读，更多相关《软件技术基础查找与排序技术（81页珍藏版）》请在装配图网上搜索。

1、在数据处理领域中，最常见的运算是在数据处理领域中，最常见的运算是在给定的数据结构中查找所需要处理的数在给定的数据结构中查找所需要处理的数据元素。据元素。另一常见的运算是对给定的数据结构另一常见的运算是对给定的数据结构进行重新分类，或按数据元素的大小重新进行重新分类，或按数据元素的大小重新进行排序，以方便对数据元素的处理。进行排序，以方便对数据元素的处理。查找与排序是数据处理的基本技术。查找与排序是数据处理的基本技术。本章主要介绍线性表查找与排序的基本方本章主要介绍线性表查找与排序的基本方法，以及索引存储结构下的查找技术。法，以及索引存储结构下的查找技术。顺序查找的基本方法是，从线性表的第一顺序

2、查找的基本方法是，从线性表的第一个元素开始，依次将线性表中的元素与被查元素个元素开始，依次将线性表中的元素与被查元素进行比较，若遇到线性表中某位置上的元素与被进行比较，若遇到线性表中某位置上的元素与被查元素相等，则表示找到（即查找成功）；若线查元素相等，则表示找到（即查找成功）；若线性表中所有的元素与被查元素进行比较都不相等，性表中所有的元素与被查元素进行比较都不相等，则表示线性表中不存在需要找的元素（即查找失则表示线性表中不存在需要找的元素（即查找失败）。败）。 对于大的线性表来说，顺序查找的效对于大的线性表来说，顺序查找的效率是很低的。率是很低的。虽然顺序查找的效率不高，但在下列虽然顺序查

3、找的效率不高，但在下列两种情况下也只能采用顺序查找。两种情况下也只能采用顺序查找。 线性表为无序表（即表中元素的排线性表为无序表（即表中元素的排列是无序的）列是无序的） 采用链式存储结构的有序线性表采用链式存储结构的有序线性表先将线性表中的元素按值非递减进行先将线性表中的元素按值非递减进行重新排列。重新排列。这样的线性表称为有序表这样的线性表称为有序表 。设有序线性表的长度为设有序线性表的长度为n，被查元素，被查元素为为x，则对分查找的方法如下。，则对分查找的方法如下。将将x与线性表的中间项进行比较：与线性表的中间项进行比较：若被查元素若被查元素x与该线性表的中间项的与该线性表的中间项的值相等

4、，则说明查到，查找结束；值相等，则说明查到，查找结束；若被查元素若被查元素x小于该线性表的中间项小于该线性表的中间项的值，则取线性表的前半部分作为子表的值，则取线性表的前半部分作为子表（即取中间项以前的部分，而不再考虑线（即取中间项以前的部分，而不再考虑线性表后半部分的元素）以相同的方法进行性表后半部分的元素）以相同的方法进行查找；查找；若被查元素若被查元素x大于该线性表的中间项大于该线性表的中间项的值，则取线性表的后半部分作为子表的值，则取线性表的后半部分作为子表（即取中间项以后的部分，而不再考虑线（即取中间项以后的部分，而不再考虑线性表前半部分的元素）以相同的方法进行性表前半部分的元素）以

5、相同的方法进行查找。查找。这个过程一直进行到查找成功或子表这个过程一直进行到查找成功或子表长度为长度为0（说明线性表中没有这个元素）（说明线性表中没有这个元素）为止。为止。当有序线性表为顺序存储时才能采用当有序线性表为顺序存储时才能采用对分查找，并且，对分查找的效率要比顺对分查找，并且，对分查找的效率要比顺序查找高得多。序查找高得多。 设表的长度为设表的长度为n。如果存在一个函数如果存在一个函数i = i(k)，对于，对于表中的任意一个元素的关键字表中的任意一个元素的关键字k，满足，满足以下条件：以下条件： 1in。 对于任意的元素关键字对于任意的元素关键字k1k2，恒存在恒存在i(k1)i(

6、k2)。则称此表为直接查找表。则称此表为直接查找表。其中函数其中函数i = i(k)称为关键字称为关键字k的映的映象函数。象函数。 对直接查找表的操作主要有以下两种对直接查找表的操作主要有以下两种Hash表技术是直接查找技术的推广，表技术是直接查找技术的推广，其主要目标是提高查找效率。其主要目标是提高查找效率。如果按照直接查找表的填入方法，填如果按照直接查找表的填入方法，填入结果如表入结果如表3.1所示。所示。 设表的长度为设表的长度为n。如果存在一个函数如果存在一个函数i = i(k)，对于，对于表中的任意一个元素的关键字表中的任意一个元素的关键字k，满，满足足1in，则称此表为，则称此表为

7、Hash表。表。其中函数其中函数i = i(k)称为关键字称为关键字k的的Hash码。码。 Hash表技术的关键是要处理好表中元表技术的关键是要处理好表中元素的冲突问题，它主要包括以下两方面的素的冲突问题，它主要包括以下两方面的工作：工作：（1）构造合适的）构造合适的Hash码，以便尽量码，以便尽量减少表中元素冲突的次数。减少表中元素冲突的次数。即即Hash码的均匀性要比较好。码的均匀性要比较好。（2）当表中元素发生冲突时，要进）当表中元素发生冲突时，要进行适当的处理。行适当的处理。在实际设计在实际设计Hash码时，要考虑以下两码时，要考虑以下两方面的因素：方面的因素： 使各关键字尽可能均匀地

8、分布在使各关键字尽可能均匀地分布在Hash表中表中 。 Hash码的计算要尽量简单。码的计算要尽量简单。比较简单的比较简单的Hash码的构造方法。码的构造方法。设线性设线性Hash表的长度为表的长度为n，对线性，对线性Hash表的查找过程如下。表的查找过程如下。线性线性Hash表的优点是简单，但它有以表的优点是简单，但它有以下两个主要缺点。下两个主要缺点。当当Hash码的冲突较多时，在线性码的冲突较多时，在线性Hash表中会存在表中会存在“堆聚堆聚”现象，即许多关键字现象，即许多关键字被连续登记在一起，从而会降低查找效率。被连续登记在一起，从而会降低查找效率。 当当Hash表的长度表的长度n设

9、计成设计成n = 2k时，还时，还可以定义另外一种可以定义另外一种Hash表表随机随机Hash表。表。 随机随机Hash表的填入与取出的过程。表的填入与取出的过程。前面所介绍的线性前面所介绍的线性Hash表与随机表与随机Hash表均存在两个致命的缺点：一是在表均存在两个致命的缺点：一是在Hash表表填入过程中不顾后效，从而在填入过程中填入过程中不顾后效，从而在填入过程中其冲突的机会在不断增多；二是当其冲突的机会在不断增多；二是当Hash表表填满时，不能正常地进行查找。填满时，不能正常地进行查找。 如果将冲突的元素安排在另外的如果将冲突的元素安排在另外的空间内，不占用空间内，不占用Hash表本身

10、的空间，表本身的空间，就不会产生新的冲突。就不会产生新的冲突。这就是溢出这就是溢出Hash表。表。溢出溢出Hash表包括表包括Hash表和溢出表和溢出表两部分。表两部分。 溢出溢出Hash表的填入与取出的过程。表的填入与取出的过程。拉链拉链Hash表又分为外链表又分为外链Hash表与内链表与内链Hash表。表。 外链外链Hash表由表由Hash表及表外结点组成。表及表外结点组成。 Hash表的第表的第i项登记着项登记着Hash码为码为i的所的所有关键字的表外结点。有关键字的表外结点。在初始状态下，在初始状态下，Hash表中的所有指针表中的所有指针为空。为空。外链外链Hash表的填入与取出过程如

11、下。表的填入与取出过程如下。填入后的外链填入后的外链Hash表如图表如图3.1所示。所示。指标指标Hash表包括指标表与内表包括指标表与内容表两部分。容表两部分。 排序是指将一个无序序列整理成按排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。值非递减顺序排列的有序序列。排序的方法有很多，根据待排序序排序的方法有很多，根据待排序序列的规模、存储结构以及对数据处理的列的规模、存储结构以及对数据处理的要求，可以采用不同的排序方法。要求，可以采用不同的排序方法。本节主要介绍针对顺序表的常用排本节主要介绍针对顺序表的常用排序法。序法。互换排序是指借助数据元素之间的互互换排序是指借助数据元素之间

12、的互相交换进行排序的一种方法。相交换进行排序的一种方法。 冒泡排序是通过相邻数据元素的交换冒泡排序是通过相邻数据元素的交换逐步将线性表变成有序。逐步将线性表变成有序。冒泡排序的基本方法如下。冒泡排序的基本方法如下。首先，从表头开始往后扫描线性表，首先，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的在扫描过程中逐次比较相邻两个元素的大小。大小。 然后，从后到前扫描剩下的线性表，然后，从后到前扫描剩下的线性表，同样，在扫描过程中逐次比较相邻两个同样，在扫描过程中逐次比较相邻两个元素的大小。元素的大小。 在上述排序过程中，对线性表的每一在上述排序过程中，对线性表的每一次来回扫描，都将其

13、中的最大者沉到了表次来回扫描，都将其中的最大者沉到了表的底部，最小者像气泡一样冒到表的前头，的底部，最小者像气泡一样冒到表的前头，冒泡排序由此而得名。冒泡排序由此而得名。冒泡排序又称下沉排序。冒泡排序又称下沉排序。图图3.2是冒泡排序的示意图。是冒泡排序的示意图。 快速排序的关键是对线性表的分割，快速排序的关键是对线性表的分割，以及对各分割出的子表再进行分割，这以及对各分割出的子表再进行分割，这个过程如图个过程如图3.3所示。所示。快速排序在最坏情况下需要快速排序在最坏情况下需要n(n 1)/2次比较，但实际的排序效率要比冒次比较，但实际的排序效率要比冒泡排序高得多。泡排序高得多。插入排序是指

14、将无序序列中的各元素依次插入排序是指将无序序列中的各元素依次插入到已经有序的线性表中。插入到已经有序的线性表中。首先将第首先将第j个元素放到一个变量个元素放到一个变量T中。然后中。然后从有序子表的最后一个元素（即线性表中第从有序子表的最后一个元素（即线性表中第j 1个元素）开始，往前逐个与个元素）开始，往前逐个与T进行比较，将大于进行比较，将大于T的元素均依次向后移动一个位置，直到发现一的元素均依次向后移动一个位置，直到发现一个元素不大于个元素不大于T为止，此时就将为止，此时就将T（即原线性表（即原线性表中的第中的第j个元素）插入到刚移出的空位置上，有个元素）插入到刚移出的空位置上，有序子表的

15、长度就变为序子表的长度就变为j了。了。图图3.4给出了插入排序的示意图。给出了插入排序的示意图。图中画有方框的元素表示刚被插入到图中画有方框的元素表示刚被插入到有序子表中。有序子表中。将整个无序序列分割成若干小的子序将整个无序序列分割成若干小的子序列分别进行插入排序。列分别进行插入排序。但这种分割不是逐段分割，而是将相但这种分割不是逐段分割，而是将相隔某个增量隔某个增量h的元素构成一个子序列。的元素构成一个子序列。在排序过程中，逐次减小这个增量，在排序过程中，逐次减小这个增量，最后当最后当h减到减到1时，进行一次插入排序，排时，进行一次插入排序，排序就完成。序就完成。图图3.5为希尔排序的示意

16、图。为希尔排序的示意图。简单选择排序的基本方法是：扫描整简单选择排序的基本方法是：扫描整个线性表，从中选出最小的元素，将它交个线性表，从中选出最小的元素，将它交换到表的最前面（这是它应有的位置）；换到表的最前面（这是它应有的位置）；然后对剩下的子表采用同样的方法，直到然后对剩下的子表采用同样的方法，直到子表空为止。子表空为止。堆的定义如下：堆的定义如下：具有具有n个元素的序列个元素的序列(h1，h2，hn)，当且仅当满足当且仅当满足i = 1，2，n/2时称之为堆。时称之为堆。 调整建堆的问题。调整建堆的问题。在调整建堆的过程中，总是将根结点在调整建堆的过程中，总是将根结点值与左、右子树的根结

17、点值进行比较，若值与左、右子树的根结点值进行比较，若不满足堆的条件，则将左、右子树根结点不满足堆的条件，则将左、右子树根结点值中的大者与根结点值进行交换。值中的大者与根结点值进行交换。这个调整过程一直做到所有子树均为这个调整过程一直做到所有子树均为堆为止。堆为止。 堆排序的方法如下：堆排序的方法如下： 首先将一个无序序列建成堆。首先将一个无序序列建成堆。 然后将堆顶元素（序列中的最大项）然后将堆顶元素（序列中的最大项）与堆中最后一个元素交换（最大项应该在与堆中最后一个元素交换（最大项应该在序列的最后）。序列的最后）。 归并归并(Merging)是将两个或两个以上的是将两个或两个以上的有序表合并

18、成一个新的有序表。有序表合并成一个新的有序表。设线性表设线性表L(1：n)中的某段中的某段L(low：high)已经部分有序，即它的两个子表已经部分有序，即它的两个子表L(low：mid)与与L(mid + 1：high)（其中（其中lowmidhigh）已经有序，现要将这两个）已经有序，现要将这两个有序子表归并成一个有序子表有序子表归并成一个有序子表L(low：high)。两个子表的归并基本做法。两个子表的归并基本做法。 开辟一个与线性表开辟一个与线性表L同样大小的表同样大小的表空间空间A。 设置三个指针设置三个指针i，j，k，其初始状，其初始状态分别指向两个有序子表的首部及表空态分别指向两

19、个有序子表的首部及表空间间A中与中与L中需要进行排序段相对应空间中需要进行排序段相对应空间的首部。的首部。即即i = low，j = mid + 1，k = low。 沿两个有序子表扫描：沿两个有序子表扫描： 将未取空的子表中的剩余元素依次将未取空的子表中的剩余元素依次放入表空间放入表空间A中。中。 将将A中的对应段复制到中的对应段复制到L中。中。图图3.9所示的为归并排序的示意图。所示的为归并排序的示意图。归并排序的算法有递归和非递归两种归并排序的算法有递归和非递归两种形式。形式。 基数排序（基数排序（Radix Sort）又称为吊桶）又称为吊桶排序，它属于分配类的排序方法。排序，它属于分配

20、类的排序方法。设线性表中各元素的关键字具有设线性表中各元素的关键字具有k位位有效数字，则基数排序的基本思想是从有有效数字，则基数排序的基本思想是从有效数字的最低位开始直到最高位，对每一效数字的最低位开始直到最高位，对每一位有效数字在线性表中进行重新排列，其位有效数字在线性表中进行重新排列，其调整的原则为：调整的原则为： 将线性表依当前位的有效数字为序将线性表依当前位的有效数字为序排列。排列。 当前位的有效数字相同时，按原次当前位的有效数字相同时，按原次序排列。序排列。这种基数排序法称为最低位优先法这种基数排序法称为最低位优先法（Least Significant Digit first，LSD

21、）。）。图图3.10是基数排序的示意图。是基数排序的示意图。从整体来看，线性表不是有序表，如从整体来看，线性表不是有序表，如果将线性表分成若干个子表，虽然每一子果将线性表分成若干个子表，虽然每一子表也不是有序的，但各个子表之间却是有表也不是有序的，但各个子表之间却是有序的，这样的线性表称为分块有序表。序的，这样的线性表称为分块有序表。分块有序表的结构可以分为两部分。分块有序表的结构可以分为两部分。 线性表本身采用顺序存储结构。线性表本身采用顺序存储结构。 再建立一个索引表。再建立一个索引表。 图图3.11是将一个长度是将一个长度n = 19的线性表分的线性表分成成m = 3个子表的分块有序表示

22、意图。个子表的分块有序表示意图。分块查找又称索引顺序查找，用于在分块查找又称索引顺序查找，用于在分块有序表中进行查找。分块有序表中进行查找。分块查找的过程可以分两步进行：分块查找的过程可以分两步进行：（1）查找索引表，以便确定被查元）查找索引表，以便确定被查元素所在子表的位置。素所在子表的位置。（2）在相应的子表中用顺序查找法）在相应的子表中用顺序查找法进行具体的查找。进行具体的查找。二叉排序树是指满足下列条件的二叉二叉排序树是指满足下列条件的二叉树：树： 左子树上的所有结点值均小于根结左子树上的所有结点值均小于根结点值；点值； 右子树上的所有结点值均不小于根右子树上的所有结点值均不小于根结点

23、值；结点值； 左、右子树也满足上述两个条件。左、右子树也满足上述两个条件。根据二叉排序树的定义，构造二叉排根据二叉排序树的定义，构造二叉排序树的过程如下：序树的过程如下：依次读入给定序列中的每一个元素，依次读入给定序列中的每一个元素，然后进行如下处理：然后进行如下处理： 若当前的二叉排序树为空，则读入若当前的二叉排序树为空，则读入的元素为根结点；的元素为根结点； 若读入的元素值小于根结点值，则若读入的元素值小于根结点值，则将元素插入到左子树中；将元素插入到左子树中； 若读入的元素值不小于根结点值，若读入的元素值不小于根结点值，则将元素插入到右子树中。则将元素插入到右子树中。例如，如果依次读入元

24、素序列例如，如果依次读入元素序列（80，82，85，75，82，68，71，77，88）中的元素，则构造二叉排）中的元素，则构造二叉排序树的过程如图序树的过程如图3.13所示所示 例如，如果将读入上述元素序列的顺例如，如果将读入上述元素序列的顺序改为（序改为（75，82，68，71，77，88，80，82，85），则构造出的二叉排序树如图），则构造出的二叉排序树如图3.14所示。所示。二叉排序树有一个重要特性：中序遍二叉排序树有一个重要特性：中序遍历二叉排序树可以得到有序序列。历二叉排序树可以得到有序序列。 从二叉排序树的根结点开始与被查值从二叉排序树的根结点开始与被查值进行比较：进行比较：

25、若被查值等于根结点值，则查找成若被查值等于根结点值，则查找成功，查找过程结束。功，查找过程结束。 若被查值小于根结点值，则到左子若被查值小于根结点值，则到左子树中去查找。树中去查找。 若被查值大于根结点值，则到右子若被查值大于根结点值，则到右子树中去查找。树中去查找。 对于经常需要动态增长且经常需对于经常需要动态增长且经常需要查找的大线性表来说，采用二叉排要查找的大线性表来说，采用二叉排序树这种结构是很方便的，它既有利序树这种结构是很方便的，它既有利于插入元素，也有利于查找。于插入元素，也有利于查找。二叉排序树实际上就是一种多层索引二叉排序树实际上就是一种多层索引树。树。 一般来说，多层索引树

26、中的每个结点一般来说，多层索引树中的每个结点包含包含2m个关键字域和个关键字域和2m + 1个指针域。个指针域。多层索引树中的结点结构如图多层索引树中的结点结构如图3.15所所示。示。B树的定义如下。树的定义如下。一棵一棵2m + 1阶的阶的B树，或为树，或为空，或为满足下列特性的度为空，或为满足下列特性的度为2m + 1的树。的树。在实际存储在实际存储B树时，为了使处理方便，树时，为了使处理方便，一般在每一个结点中还增加两个域：一个一般在每一个结点中还增加两个域：一个用于记录本结点中实际的关键字个数；另用于记录本结点中实际的关键字个数；另一个用于指向父结点。一个用于指向父结点。由由B树的定义

27、可知，在树的定义可知，在B树中进行查树中进行查找的过程与二叉排序树的查找很类似。找的过程与二叉排序树的查找很类似。 B树查找的效率取决于树查找的效率取决于B树的深度以树的深度以及结点中的元素数目。及结点中的元素数目。 在在2m + 1阶的阶的B树中插入一个新元素树中插入一个新元素x，首先要进行查找，以便找到元素，首先要进行查找，以便找到元素x在叶在叶子结点中应插入的位置。子结点中应插入的位置。如果在查找过程中发现如果在查找过程中发现B树中已经存树中已经存在元素在元素x，则表示出错，这是因为在，则表示出错，这是因为在B树树一般不允许存在两个相等的元素；否则根一般不允许存在两个相等的元素；否则根据

28、找到的插入位置（参看据找到的插入位置（参看B树的查找），树的查找），将元素将元素x插入，并保持有序排列。插入，并保持有序排列。 图图3.17给出了在给出了在B树中进行插入树中进行插入的示意图。的示意图。要在要在B树中删除一个指定的元素树中删除一个指定的元素x，首先也要进行查找，找到元素，首先也要进行查找，找到元素x在在B树中的位置。树中的位置。如果要删除的元素如果要删除的元素x在在B树的叶子结树的叶子结点上，则进行删除；如果要删除的元素点上，则进行删除；如果要删除的元素x不在叶子结点上，则要用一个比不在叶子结点上，则要用一个比x大、而大、而又最接近又最接近x的元素的元素y代替代替x（即删除了元

29、素（即删除了元素x），显然，这个），显然，这个y就是就是x右边指针所指的右边指针所指的路径上最左边叶子结点上的第一个元素，路径上最左边叶子结点上的第一个元素，然后在叶子结点中删除然后在叶子结点中删除y。由此可以看出，由此可以看出，B树的删除都归结为树的删除都归结为在叶子结点上删除一个元素。在叶子结点上删除一个元素。在在B+树中，所有的元素均按递增顺树中，所有的元素均按递增顺序从左到右被安排在叶子结点上，各叶序从左到右被安排在叶子结点上，各叶子结点之间从左到右用指针（利用叶子子结点之间从左到右用指针（利用叶子结点中的最后一个指针域）链接起来。结点中的最后一个指针域）链接起来。图图3.18是一个是一个B+树的模型。树的模型。图图3.19所示的是一棵所示的是一棵5阶（阶（m = 2）的）的B+树。树。B+树的查找分随机查找与顺序查找树的查找分随机查找与顺序查找两种。两种。B+树的插入与树的插入与B树的插入过程也树的插入过程也基本相同。基本相同。 在在B+树中删除一个元素要比树中删除一个元素要比B树树简单，这也是简单，这也是B+树的优点之一。树的优点之一。 拓扑分类是指对一个序列按需要拓扑分类是指对一个序列按需要的顺序进行重新排列。的顺序进行重新排列。拓扑分类也称拓扑排序。拓扑分类也称拓扑排序。