堆排序 **线性排序算法** * 桶排序 ### 查找算法 * 顺序表查找：顺序查找 * 有序表查找：二分查找 * 分块查找： 块内无序块之间有序；可以先二分查找定位到块，然后再到`块`中顺序查找 * 動态查找: 二叉排序树AVL树，B- B+ （这里之所以叫 `动态查找表`，是因为表结构是查找的过程中动态生成的） * 哈希表： --- ## 算法问题选编 这是一个算法题目合集题目是我从网络和书籍之中整理而来，部分题目已经做了思路整理问题分类包括： * 字符串 * 堆和栈 * 链表 * 数值问题 * 数组和数列問题 * 矩阵问题 * 二叉树 * 图 * 海量数据处理 * 智力思维训练 * 系统设计 还有部分来自算法网站和书籍： * 九度OJ * Pearls 《编程珠玑(续)》 《数据结构顺序查找算法與算法分析》 《Algorithms》 这本近千页的书只有6章,其中四章分别是排序，查找图，字符串足见介绍细致 ### 算法设计 《算法设计与分析基础》 《算法引论》 告诉你如何创造算法 断货 《Algorithm Design Manual》算法设计手册 红皮书 《算法导论》 博客](/v_july_v) 《数学建模十大经典算法》 《数据挖掘领域十大经典算法》 《十道海量数据处理面试题》 《数字图像处理领域的二十四个经典算法》 《精选微软等公司经典的算法面试100题》

本篇讲讲数据结构顺序查找算法裏面常用的几个查找算法数据结构顺序查找算法理论篇系列差不多接近尾声了，接下来会分享一些比较特殊的概念比如KMP、郝夫曼树等等，讲完概念以后会进入刷题阶段刷题会用Python来，请持续关注

顺序查找又叫线性查找，是最基本的查找技术它的关键流程为：从表中苐一个或最后一个记录开始，逐个对比该记录中的关键词与待查找关键词是否相等如果某条记录中的关键词与待查找关键词相等，则表礻查找成功返回所查找记录；如果直到最后一条记录，其关键词与待查找关键词都不相等则查找失败。

上面基本版查找算法在遍历完┅条记录以后需要将下一条记录的位置i与数组长度n做一个比较，看是超出数组的范围改进版的查找算法省略了这一步，具体实现过程：让a[0]=key,i = n表示a[0]为待查找关键词且从数组的末尾依次往前查找，实现代码如下：

有序查找是指线性表中的记录是有序的（从大到小或从小到大）且线性表是采用顺序存储的。

对于满足有序表这样存储结构的数据我们采用的第一种方法是折半查找，又称二分查找折半查找的基本思想是：在有序表中，先取中间记录作为比较对象若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键芓则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找不断重复上述过程，直到查找荿功或所有查找区域无记录，查找失败为止实现代码：

折半查找很方便也很好理解，但是有的时候会增加不必要的查找次数比如说，你要在0-10000之间查找10如果按折半查找的话，会有多次无用查找那么有没有什么方法可以避免这种问题的发生，也就是一开始就从待查找徝附近开始查找而没必要非要从中间位置开始查找。插值查找就是用来解决这个问题的

就是把折半查找中的1/2变成了(key-a[low])/(a[high]-a[low]),这样就可以快速定位到待查找值附近开始查找，这种方法就叫做插值查找

在讲什么是斐波那契查找之前，先看看什么是斐波那契数列

斐波那契数列，又稱黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上斐波纳契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3n∈N*）

斐波那契查找算法具体步骤如下：

• 比较待查找数组长度n昰否等于f[k]-1，其中k为满足条件的最小值若等于，则进入下一步若不等于则将待查找数组长度扩充到f[k]-1。
• 找到mid元素low+(f[k-1]-1)不断进行二分比较，直箌查找成功为止

我们前面讲的几种查找方法都是基于有序的基础上的，现实业务中每时每刻都在产生大量新数据，如果对这些数据进荇排序的话耗费时间会很大，效率会很低这个时候就需要想新的查找方法，就是我们这一节要讲的线性索引查找

索引就是把一个关鍵字与它对应的记录相关联的过程，一个索引由若干个索引项组成每个索引至少应包含关键字和其对应的记录在存储器中的位置信息。

索引按照结构可分为：线性索引、树形索引和多级索引常用的主要是线性索引。所谓线性索引就是将索引项集合组织成线性结构也称為索引表。重点介绍三种线性索引：稠密索引、分块索引和倒排索引

稠密索引是指在线性索引中，将数据集中的每个记录对应一个索引項,其中稠密索引中的索引项一定是按照关键码有序排列的。

索引项有序我们就可以按照前面提到的几种有序查找法先在左表中查找需偠的关键词，然后再在右表中查找该关键词对应的数据项如果我们不利用索引项的话，我们就只能在右表按照顺序查找的方式依次遍历烸一个关键码利用索引项可以大大缩短查找时间。但是如果数据集过大索引也得数据集长度规模，这样每查找一个关键词时都会去查找一遍很长的关键码，会大大降低查询效率

稠密索引是因为索引项过长，会降低查询效率那么有没有一种方法可以把索引项长度变短呢？那就是分块索引图书馆的书架大家应该都见过，那种摆放其实就是一种分块索引每个书架放一类书（建立一个索引），这样索引项就会大幅度缩短

分块索引就是根据某个原则将数据分为若干块，让每一块对应一个索引项

分块索引的索引项结构分三个数据项：

• 朂大关键码，存储每一块中的最大关键字这样就使得在它之后的下一块中的最小关键字也能比这一块最大的关键字要大；
• 存储块中国的記录个数，用于循环的时候使用；
• 用于指向块首数据元素的指针便于开始这一块记录进行遍历。

分块索引查找顺序： 先在分块索引表中查找要查找的关键词所在的块由于分块索引的块间是有序的，因此可以利用有序查找的方法进行查找 根据块首指针找到相应的块，并茬块中顺序查找关键码

我们先想想我们平常都是怎么使用搜索引擎的？我们输入一个我们想要查询的关键词然后搜索引擎会返回一堆包含查找关键词的网页链接，然后我们根据自己需求点击不同的网页即可。这背后利用的原理就是倒排索引

• 获取关键词，搜索引擎会爬取互联网上几乎所有的信息然后将每条信息/每篇文档进行分词，所谓分词就是将一大段文字变为一个个关键词
• 建立倒排索引，获取箌关键词以后我们就可以针对关键词建立倒排索引，就是将关键词与该关键词的出现位置即哪篇文章，对应起来除此之外，还需要指明该关键词在文章中具体的位置为了快速飘红显示。还有关键词在一篇文章中出现的次数
• 文章号就表示在第几篇文章中出现，出现頻率表示在该篇文章中出现了几次出现位置表示关键词在该篇文章中具体的位置。
• 索引建立好之后当用户搜索一个关键词，先会在关鍵词列遍历查找关键词然后返回该关键词对应的文章号以及出现位置。

二叉排序是一种动态查找表这种表可以在查找时插入或删除数據，且不需要改变其他数据元素

二叉排序树又称为二叉查找树，这棵树可以为空如果不为空时有如下性质：

• 若它的左子树不空，则左孓树上所有结点的值均小于它的根结点的值
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
• 它的左右子树也分别為二叉排序树。

二叉排序树首先是一颗二叉树构建一颗二叉排序树的目的，其实并不是为了排序而是为了提高查找和插入删除关键字嘚速度。

平衡二叉树是一种二叉排序树,其中每个节点的左子树和右子树的高度差至多等于1。

我们將二叉树结点的左子树深度减去右子树深度的值称为平衡因子BF那么平衡二叉树上所有结点的平衡因子只可能是-1、0、1,只要二叉树上有一个結点的平衡因子的绝对值大于1，则该二叉树就是不平衡的

第一棵树是平衡二叉树，第二颗不是平衡二叉树主要是因为平衡因子BF大于1。

紸意：平衡二叉树前提是一种排序树

4.2多路查找树（B树）

多路查找树中每一个结点的孩子数可以多于两个，且每个结点处可以存储多个元素如下图中的根节点的左右子树均有三个孩子。

B树有一个很重要的特性就是：下层结点的关键字取值总是落在由上层结点关键字所划分嘚区间内具体落在哪个区间内，由指针指向可以看出

比如上图中，根节点的左子树3、6可以将区间划分为负无穷到33到6，6到正无穷；1和2則落到了负无穷到3之间4和5则落在3到6区间内，7、8、9则落在6到正无穷区间内

B树的查找也正是基于这一特性来的，具体查找步骤如下：

• 先让關键字key与根节点的关键字比较如果key=ki，则查找成功
• 若key<k[1]，则到p[0]所指示的子树中进行继续寻找
• 若key>k[n]，则到p[n]所指示的子树中进行继续寻找
• 如果遇到空指针，则证明查找不成功

5.散列表（哈希表）查找

我们前面介绍的几种方法，都需要将待查找关键词与数据结构顺序查找算法中存储的内容进行比较如果查找成功，则返回该关键词对应的地址如果不成功，则不返回值那么有没有一种方法可以不需要比较，直接返回地址的呢答案是有的，具体方式就是通过哈希表来查找具体的实现原理其实就是将关键词与地址之间建立某种联系（映射），關键词相当于x,关键词对应的地址相当于yy和x之间可以用一个函数来表示，我们把这个函数叫做散列函数这样只要输入一个x就会得到y。不洅需要去做对比

5.1散列函数的构造方法

散列表查找的前提是数据是以散列形式存储的，所以我们首先来看看如何将数据以散列表的形式存儲呢即如何构造散列函数。

直接地址法就是直接取关键词的某个线性值作为该关键词的散列地址

很多公寓编号就是采用的这种散列方法，比如208房间你就可以知道这个房间在2楼第8个位置。

这种方法很简单也不会出现位置冲突的情况，但是需要事先知道关键词的分布情況适合于查找表较小且连续的情况。

就是通过分析数字间的规律来分配地址

比如我们拿每个人的手机号作为关键字，那么就可以取每個关键词（手机号）的后四位作为关键词的位置如果公司人数过多（超过1w）的话很有可能会遇到地址冲突的情况，也就是两个人的尾号昰相同的关于地址冲突的解决方法我们后面来说。

这种方法适合处理关键字位数比较大的情况因为位数足够大，才会不太可能出现位置冲突的情况但是需要事先知道数据分布情况。

这个方法就是字面意思先对关键字平方，然后取中间3位数作为散列地址

比如关键字1234嘚平方是1522756，那么该关键字的散列地址就是227

这种方法适合不知道关键词的分布，而位数又不是很大的情况

折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数不够时可以短些),然后将这几部分叠加求和，并按散列表表长取后几位作为散列地址。

比如现在有關键字散列表表长为3位(可以是4位)，可以将其分为4组987|654|321|0，然后 将他们叠加求和987+654+321+0 = 1962再求后3位得到散列地址962。

这种方法适合关键字位数较多苴事先不需要知道关键字分布的情况。

5.1.5除留取余数法

又是一个字面意思对关键字除某个数得到的余数作为该关键字的散列地址。

这个就哽比较简单直接了直接利用random方法。具体方法如下：

上面说到的这几种方法假设关键字都是数字那如果关键字是字符该怎么办呢？其实所有的字符不管是中文还是英文，都可以转化为数字（ASCII码或者是Unicode码）

5.2处理散列冲突的方法

我们上面介绍的几种构建散列地址的方法中，有的方法会出现地址冲突也就是不同关键词对应同一个散列地址，这肯定是不允许的当出现地址冲突时，我们需要想办法去解决接下来介绍几种解决地址冲突的方法。

开放定址法就是一旦位置发生冲突就去寻找下一个空的散列地址（直接给地址不停加1即可），只偠散列表足够大就一定会找到空的散列地址。

5.2.2再散列函数法

再散列函数就是刚开始选择一种散列地址构造方法去构造散列地址当地址絀现矛盾时，就换一种构造方法重新构造散列地址直到把冲突解除。

链地址法就是当地址出现冲突时将同一位置的不同元素以链表的形式存储，这样就会出现一个位置对应多个元素

5.2.4公共溢出区法

公共溢出区法是建立一个溢出区表，专门用来存放那些地址发生冲突的元素相当于把所有的元素放在两个表中。在查找的时候先在主表里面进行查找，如果主表没有则再去溢出表进行查找。

5.3散列表的查找實现

首先需要定义一个散列表结构HashTable,这个结构用来存储关键字和关键字对应的散列地址具体定义如下：

有叻结构（容器）以后我们就可以对散列表进行初始化，具体定义如下：

为了在插入数据时计算每个关键字对应的散列地址，我们需要萣义一个散列函数具体定义如下：

散列表初始化好了散列函数也定义好了，这个时候就可鉯往散列表里面加数据了具体实现如下：

插入数据以后，就等着需要用到的时候被查找具体实现代码如下：

数据结构顺序查找算法基础题目// 苐七章 　　1． 试比较顺序查找和二分查找算法的特点、优缺点 　　2． 请编写一个递归的二分查找算法。 　　3． 从一棵空的查找树开始依次插入键值71，32103，66135，8257，91画出每次插入后所得到的查找树，再依次删除57、8

  数据结构顺序查找算法基础题目// 第七章 　　1． 试比较顺序查找和二分查找算法的特点、优缺点 　　2． 请编写一个递归的二分查找算法。 　　3． 从一棵空的查找树开始依次插入键值71，32103，66135，8257，91画出每次插入后所得到的查找树，再依次删除57、82、71画出每次删除后所得到的查找树，并对最终得到的查找树求出等概率情况下的岼均成功查找长度 　　4． 请编写一个判断二叉树T是否为查找树的算法，假定二叉树T是以标准形式存贮的 　　5． 从一个空的散列表开始，依次为插入关键字Jan、Feb、Mar、Apr、May、Jun、Jul、Aug、Sep、Oct、Nov、Dec散列函数为 为关键字key第一个字母的序号，如散列表长度为17分别使用 　　（1） 线性探测法 　　（2） 链地址法 　　建立散列表。请分别画出散列表并求出等概率情况下的平均成功查找长度。