算法找东西

1. 高分求算法：寻找与特定对象距离最近的对象

用现在的ID,X,Y三个元素来找最近点的话无论什么办法,都至少要与每个点进行一次距离的判断,比较X或者Y也好,计算距离(当然这个距离是不用开平方的,与其他所有点的距离都不开平方也能比较相对的距离长短)也好,所以如果只有这三个元素的话,其实再怎么改也不会有太大的优化的。

最好还是添加一些辅助信息，比较常用的就是以划分网格的方法，将所有点分派在不同的网格中，然后以网格为基础找最近点，这样的话就要加一个网格的结构（以空间换时间），里面存放的就是属于这个网格的点的ID，通过编号规则可以很快的找最近的网格，然后再找里面的点，这样可以提高点查找速度。

呵呵,不好意思,没想清楚就写了:P,改一下,改一下,再加一步就好了

1.给点添加一个所属网格的信息:
Class A
{
public int ID;
public int X;
public int Y;
publci int Index;//所属网格编号
}
2.构造一个点链表,这是为了减少空间和方便处理而加的,后面的算法里会感觉到用处
(为每个点对象建立一个点链表节点)
Class I
{
public A *pAObject; //指向一个点对象
publci I *pNextA; //指向下一个
}
3.构件一个网格信息结构
Class G
{
public int ID; //网格编号
public I *pAObjects; //指向一个点链表(至于这个是带头节点还是不带头节点的都一样啦)
//这里用链表比较好
//第一,因为点可移动,那么点对象个数可以随意,可以发挥链表的扩展性
//第二,不需要取中间节点,也就没有用到数组的长处
}
4.构建网格,比如以1000为长度(长度可以自己定义,关键是平衡空间和速度关系),建立正方形的网格,那么(0,0)到(1000000,1000000)就是有1000*1000个网格(在给网格编号的时候最好有规律,那么就能通过List或者其他数组容器的下标来获得网格信息)
5.添加点的时候,先判断属于哪个网格,然后在点信息中添加网格编号,同时构建对应的点链表节点,并添加到所属网格的链表中
6.最后就是查询点了,首先获得出发点中的所属网格信息,看这个网格中是否有其他点:有,则一个个的判断距离(距离的平方),那么最近点一定在这些点里面(如果点还是太多,那么就考虑缩小网格的范围);没有,那就找所属网格周边8个网格中是否有点,有,则再找最近点,没有就再往外扩(如果感觉网格太多,可以加大网格的范围)
7.以找到的最近点到出发点的距离为基准,看看出发点到周边网格在这个距离内会接触到的(没有在6中遍历过的)有几个网格,把这些网格中的点再查看有没有更近的就行了

注:
1.如果还要优化就是加大网格的层次,可以用多层网格,这就会更复杂一点
2.在网格信息结构(G)中,因为点会移动,那么删点链表节点会有一个查找过程,如果觉得这个慢,那么就在点对象结构体中加一个所属点链表的指针:
class I;
Class A
{
public int ID;
public int X;
public int Y;
publci int Index;//所属网格编号
publci I *pI;
}
....

呵呵，看了lipai006的回答，想了下似乎也是可以实现的，只要多花点内存就可以达到比较好的速度了，而且也不需要真的从X坐标出发这样慢慢的以扇形扩展了啦，通过做一些辅助结构，就直接可以从出发点的X坐标出发，找同X不同Y中Y坐标与出发点最近的就行啦，循环结束条件就是X的扩展距离已经大于当前最小距离，因为再往外也肯定比当前最小距离大了。这个方法也就是要更复杂一些的辅助结构做索引，添加点的时候也要多做些事情，而且实现上的代码相对网格方法复杂一些，但查找速度应该比网格会快一点，因为毕竟是直接找点去了，其实网格方法就是把一批点的X，Y坐标看成是一样的，这样先过滤一批而已，是个速度与复杂度的折中。

xx_lzj:划分区域的目的就是为了使每个区域内的点不能太多，根据我的结构，每个区域有没有点，一个bool判断就够了，不会存在太稀疏影响效率的事情，不过最坏的情况的确会退化到遍历整个点空间，所以这个方法的时间复杂度仍然是O(n)。
你的方法其实和lipai006说的原理是差不多的（如果我对你们链表结构的猜想准确的话），无非就是通过X,Y坐标形成一个二维双向链表，在形成这个链表的过程会比网格相对复杂一点，而且也不是像你想的只要判断8个点就够的，当只有一个点在中间，其他点分布成以这个点为圆心的圆周上时，按照贴主的要求，难道只有8个最近点吗？？在这个情况下，你的最坏复杂度还是O(n)，但就如我说过的，这个方法的平均时间复杂度在参数上是会比网格的低一点，但是算法本身的代码复杂度上会高一点，而且在插入点的过程中的时间消耗会大一点而已。我觉得这是一个整体的过程，不能为了查找的快速牺牲太多其他的时间。
*************
xx_lzj:不好意思，你的链表我还有些不明白的地方:1.二维双向链表每个节点有4个指针，你能否把这4个指针如何获得的说一下，最好不要取边界线上的点，取中间的一个点进行介绍。2.对于初始化和修改点坐标的时候，现有数据如果是链表结构（不是数组），如何能不依靠其他辅助数据进行折半查找？3.修改某个点坐标之后，根据你的链表结构，我感觉不是删除、插入节点这么简单的，能不能具体点说明。

2. 常见查找和排序算法

查找成功最多要n 次，平均（n+1）/2次， 时间复杂度为O(n) 。
优点：既适用顺序表也适用单链表，同时对表中元素顺序无要求，给插入带来方便，只需插入表尾即可。
缺点：速度较慢。

改进：在表尾设置一个岗哨，这样不用去循环判断数组下标是否越界，因为最后必然成立。

适用条件：

二分查找的判定树不仅是二叉排序树，而且是一棵理想平衡树。 时间复杂度为O(lbn) 。

循环实现

递归实现

待排序的元素需要实现 Java 的 Comparable 接口，该接口有 compareTo() 方法，可以用它来判断两个元素的大小关系。

从数组中选择最小元素，将它与数组的第一个元素交换位置。再从数组剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。不断进行这样的操作，直到将整个数组排序。

选择排序需要 ~N2/2 次比较和 ~N 次交换，==它的运行时间与输入无关==，这个特点使得它对一个已经排序的数组也需要这么多的比较和交换操作。

从左到右不断 交换相邻逆序的元素 ，在一轮的循环之后，可以让未排序的最大元素上浮到右侧。

在一轮循环中，如果没有发生交换，那么说明数组已经是有序的，此时可以直接退出。

每次都 将当前元素插入到左侧已经排序的数组中 ，使得插入之后左侧数组依然有序。

对于数组 {3, 5, 2, 4, 1}，它具有以下逆序：(3, 2), (3, 1), (5, 2), (5, 4), (5, 1), (2, 1), (4, 1)，插入排序每次只能交换相邻元素，令逆序数量减少 1，因此插入排序需要交换的次数为逆序数量。

==插入排序的时间复杂度取决于数组的初始顺序，如果数组已经部分有序了，那么逆序较少，需要的交换次数也就较少，时间复杂度较低==。

对于大规模的数组，插入排序很慢，因为它只能交换相邻的元素，每次只能将逆序数量减少 1。希尔排序的出现就是为了解决插入排序的这种局限性，它通过交换不相邻的元素，每次可以将逆序数量减少大于 1。

希尔排序使用插入排序对间隔 h 的序列进行排序。通过不断减小 h，最后令 h=1，就可以使得整个数组是有序的。

希尔排序的运行时间达不到平方级别，使用递增序列 1, 4, 13, 40, ... 的希尔排序所需要的比较次数不会超过 N 的若干倍乘于递增序列的长度。后面介绍的高级排序算法只会比希尔排序快两倍左右。

归并排序的思想是将数组分成两部分，分别进行排序，然后归并起来。

归并方法将数组中两个已经排序的部分归并成一个。

将一个大数组分成两个小数组去求解。

因为每次都将问题对半分成两个子问题，这种对半分的算法复杂度一般为 O(NlogN)。

先归并那些微型数组，然后成对归并得到的微型数组。

取 a[l] 作为切分元素，然后从数组的左端向右扫描直到找到第一个大于等于它的元素，再从数组的右端向左扫描找到第一个小于它的元素，交换这两个元素。不断进行这个过程，就可以保证左指针 i 的左侧元素都不大于切分元素，右指针 j 的右侧元素都不小于切分元素。当两个指针相遇时，将切分元素 a[l] 和 a[j] 交换位置。

快速排序是原地排序，不需要辅助数组，但是递归调用需要辅助栈。

快速排序最好的情况下是每次都正好将数组对半分，这样递归调用次数才是最少的。这种情况下比较次数为 CN=2CN/2+N，复杂度为 O(NlogN)。

最坏的情况下，第一次从最小的元素切分，第二次从第二小的元素切分，如此这般。因此最坏的情况下需要比较 N2/2。为了防止数组最开始就是有序的，在进行快速排序时需要随机打乱数组。

因为快速排序在小数组中也会递归调用自己，对于小数组，插入排序比快速排序的性能更好，因此在小数组中可以切换到插入排序。

最好的情况下是每次都能取数组的中位数作为切分元素，但是计算中位数的代价很高。一种折中方法是取 3 个元素，并将大小居中的元素作为切分元素。

对于有大量重复元素的数组，可以将数组切分为三部分，分别对应小于、等于和大于切分元素。

三向切分快速排序对于有大量重复元素的随机数组可以在线性时间内完成排序。

快速排序的 partition() 方法，会返回一个整数 j 使得 a[l..j-1] 小于等于 a[j]，且 a[j+1..h] 大于等于 a[j]，此时 a[j] 就是数组的第 j 大元素。

可以利用这个特性找出数组的第 k 大的元素。

该算法是线性级别的，假设每次能将数组二分，那么比较的总次数为 (N+N/2+N/4+..)，直到找到第 k 个元素，这个和显然小于 2N。

堆中某个节点的值总是大于等于其子节点的值，并且堆是一颗完全二叉树。

堆可以用数组来表示，这是因为堆是完全二叉树，而完全二叉树很容易就存储在数组中。位置 k 的节点的父节点位置为 k/2，而它的两个子节点的位置分别为 2k 和 2k+1。这里不使用数组索引为 0 的位置，是为了更清晰地描述节点的位置关系。

在堆中，当一个节点比父节点大，那么需要交换这个两个节点。交换后还可能比它新的父节点大，因此需要不断地进行比较和交换操作，把这种操作称为上浮。

类似地，当一个节点比子节点来得小，也需要不断地向下进行比较和交换操作，把这种操作称为下沉。一个节点如果有两个子节点，应当与两个子节点中最大那个节点进行交换。

将新元素放到数组末尾，然后上浮到合适的位置。

从数组顶端删除最大的元素，并将数组的最后一个元素放到顶端，并让这个元素下沉到合适的位置。

把最大元素和当前堆中数组的最后一个元素交换位置，并且不删除它，那么就可以得到一个从尾到头的递减序列，从正向来看就是一个递增序列，这就是堆排序。

一个堆的高度为logN，因此在堆中插入元素和删除最大元素的复杂度都为 logN。

对于堆排序，由于要对 N 个节点进行下沉操作，因此复杂度为 NlogN。

堆排序是一种原地排序，没有利用额外的空间。

现代操作系统很少使用堆排序，因为它无法利用局部性原理进行缓存，也就是数组元素很少和相邻的元素进行比较和交换。

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，==计数排序要求输入的数据必须是有确定范围的整数==。

当输入的元素是 n 个 0 到 k 之间的整数时，它的==运行时间是 O(n + k)==。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。比较适合用来排序==小范围非负整数数组的数组==。

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

当输入数据均匀分配到每一个桶时最快，当都分配到同一个桶时最慢。

实间复杂度N*K

快速排序是最快的通用排序算法，它的内循环的指令很少，而且它还能利用缓存，因为它总是顺序地访问数据。它的运行时间近似为 ~cNlogN，这里的 c 比其它线性对数级别的排序算法都要小。

使用三向切分快速排序，实际应用中可能出现的某些分布的输入能够达到线性级别，而其它排序算法仍然需要线性对数时间。

3. 目标检测算法图解：一文看懂RCNN系列算法

姓名：王咫毅

学号：19021211150

【嵌牛导读】CNN如此风靡，其衍生算法也是层出不穷，各种衍生算法也可以应用于各种应用场景，各类场合。本文则是了解每个衍生算法的各个使用场景、原理及方法。

【嵌牛鼻子】RCNN 目标检测

【嵌牛提问】RCNN系列算法有何区别和联系？

【嵌牛正文】

在生活中，经常会遇到这样的一种情况，上班要出门的时候，突然找不到一件东西了，比如钥匙、手机或者手表等。这个时候一般在房间翻一遍各个角落来寻找不见的物品，最后突然一拍大脑，想到在某一个地方，在整个过程中有时候是很着急的，并且越着急越找不到，真是令人沮丧。但是，如果一个简单的计算机算法可以在几毫秒内就找到你要找的物品，你的感受如何？是不是很惊奇！这就是对象检测算法（object detection）的力量。虽然上述举的生活例子只是一个很简单的例子，但对象检测的应用范围很广，跨越多个不同的行业，从全天候监控到智能城市的实时车辆检qian测等。简而言之，物体检测是强大的深度学习算法中的一个分支。

在本文中，我们将深入探讨可以用于对象检测的各种算法。首先从属于RCNN系列算法开始，即RCNN、 Fast RCNN和 Faster RCNN。在之后的文章中，将介绍更多高级算法，如YOLO、SSD等。

1.解决对象检测任务的简单方法（使用深度学习）

下图说明了对象检测算法是如何工作。图像中的每个对象，从人到风筝都以一定的精度进行了定位和识别。

下面从最简单的深度学习方法开始，一种广泛用于检测图像中的方法——卷积神经网络（CNN）。如果读者对CNN算法有点生疏，建议 阅读此文 。

这里仅简要总结一下CNN的内部运作方式：

首先将图像作为输入传递到网络，然后通过各种卷积和池化层处理，最后以对象类别的形式获得输出。

对于每个输入图像，会得到一个相应的类别作为输出。因此可以使用这种技术来检测图像中的各种对象。

1.首先，将图像作为输入；

2.然后，将图像分成不同的区域；

3.然后，将每个区域视为单独的图像；

4.将所有这些区域传递给CNN并将它们分类为各种类别；

5.一旦将每个区域划分为相应的类后，就可以组合所有这些区域来获取具有检测到的对象的原始图像：

使用这种方法会面临的问题在于，图像中的对象可以具有不同的宽高比和空间位置。例如，在某些情况下，对象可能覆盖了大部分图像，而在其他情况下，对象可能只覆盖图像的一小部分，并且对象的形状也可能不同。

基于此，需要划分大量的区域，这会花费大量的计算时间。因此，为了解决这个问题并减少区域数量，可以使用基于区域的CNN，它使用提议方法选择区域。

2.基于区域的卷积神经网络

2.1 RCNN的思想

RCNN算法不是在大量区域上工作，而是在图像中提出了一堆方框，并检查这些方框中是否包含任何对象。RCNN 使用选择性搜索从图像中提取这些框。

下面介绍选择性搜索以及它如何识别不同的区域。基本上四个区域形成一个对象：不同的比例、颜色、纹理和形状。选择性搜索在图像中识别这些模式，并基于此提出各种区域。以下是选择性搜索如何工作的简要概述：

首先， 将图像作为输入：

然后，它生成初始子分段，以便获得多个区域：

之后，该技术组合相似区域以形成更大的区域（基于颜色相似性、纹理相似性、尺寸相似性和形状兼容性）：

最后，这些区域产生最终的对象位置（感兴趣的区域）；

下面是RCNN检测对象所遵循的步骤的简要总结：

1.首先采用预先训练的卷积神经网络；

2.重新训练该模型模型——根据需要检测的类别数量来训练网络的最后一层（迁移学习）；

3.第三步是获取每个图像的感兴趣区域。然后，对这些区域调整尺寸，以便其可以匹配CNN输入大小；

4.获取区域后，使用SVM算法对对象和背景进行分类。对于每个类，都训练一个二分类SVM；

最后，训练线性回归模型，为图像中每个识别出的对象生成更严格的边界框；

[对上述步骤进行图解分析]（ http://www.robots.ox.ac.uk/~tvg/publications/talks/Fast-rcnn-slides.pdf ）：

首先，将图像作为输入：

然后，使用一些提议方法获得感兴趣区域（ROI）（例如，选择性搜索）：

之后，对所有这些区域调整尺寸，并将每个区域传递给卷积神经网络：

然后，CNN为每个区域提取特征，SVM用于将这些区域划分为不同的类别：

最后，边界框回归（Bbox reg）用于预测每个已识别区域的边界框：

以上就是RCNN检测物体的全部流程。

2.2 RCNN的问题

从上节内容可以了解到RCNN是如何进行对象检测的，但这种技术有其自身的局限性。以下原因使得训练RCNN模型既昂贵又缓慢：

基于选择性搜索算法为每个图像提取2,000个候选区域；

使用CNN为每个图像区域提取特征；

RCNN整个物体检测过程用到三种模型：

CNN模型用于特征提取；

线性svm分类器用于识别对象的的类别；

回归模型用于收紧边界框；

这些过程相结合使得RCNN非常慢，对每个新图像进行预测需要大约40-50秒，这实际上使得模型在面对巨大的数据集时变得复杂且几乎不可能应用。

好消息是存在另一种物体检测技术，它解决了RCNN中大部分问题。

3.了解Fast RCNN

3.1Fast RCNN的思想

RCNN的提出者Ross Girshick提出了这样的想法，即每个图像只运行一次CNN，然后找到一种在2,000个区域内共享该计算的方法。在Fast RCNN中，将输入图像馈送到CNN，CNN生成卷积特征映射。使用这些特征图提取候选区域。然后，使用RoI池化层将所有建议的区域重新整形为固定大小，以便将其馈送到全连接网络中。

下面将其分解为简化概念的步骤：

1.首先将图像作为输入；

2.将图像传递给卷积神经网络，生成感兴趣的区域；

3.在所有的感兴趣的区域上应用RoI池化层，并调整区域的尺寸。然后，每个区域被传递到全连接层的网络中；

4.softmax层用于全连接网以输出类别。与softmax层一起，也并行使用线性回归层，以输出预测类的边界框坐标。

因此，Fast RCNN算法中没有使用三个不同的模型，而使用单个模型从区域中提取特征，将它们分成不同的类，并同时返回所标识类的边界框。

对上述过程进行可视化讲解：

将图像作为输入：

将图像传递给卷积神经网络t，后者相应地返回感兴趣的区域：

然后，在提取的感兴趣区域上应用RoI池层，以确保所有区域具有相同的大小：

最后，这些区域被传递到一个全连接网络，对其进行分类，并同时使用softmax和线性回归层返回边界框：

上述过程说明了Fast RCNN是如何解决RCNN的两个主要问题，即将每个图像中的1个而不是2,000个区域传递给卷积神经网络，并使用一个模型来实现提取特征、分类和生成边界框。

3.2Fast RCNN的问题

Fast RCNN也存在一定的问题，它仍然使用选择性搜索作为查找感兴趣区域的提议方法，这是一个缓慢且耗时的过程，每个图像检测对象大约需要2秒钟。

因此，又开发了另一种物体检测算法——Faster RCNN。

4.了解Faster RCNN

4.1. Faster RCNN的思想

Faster RCNN是Fast RCNN的修改版本，二者之间的主要区别在于，Fast RCNN使用选择性搜索来生成感兴趣区域，而Faster RCNN使用“区域提议网络”，即RPN。RPN将图像特征映射作为输入，并生成一组提议对象，每个对象提议都以对象分数作为输出。

以下步骤通常采用Faster RCNN方法：

1.将图像作为输入并将其传递给卷积神经网络，后者返回该图像的特征图；

2.在这些特征图上应用RPN，返回提议对象及其分数；

3.在这些提议对象上应用RoI池层，以将所有提案降低到相同的大小；

4.最后，将提议传递到全连接层，该层在其顶部具有softmax层和线性回归层，以对对象的边界框进行分类和输出；

这里简要解释一下RPN是如何运作的：

首先，Faster RCNN从CNN获取特征图并将它们传递到区域提议网络。RPN在这些特征图上使用滑动窗口，每个窗口生成不同形状和大小的k个方框（ Anchor boxe）：

方框是固定尺寸的边界箱，具有不同的形状和尺寸。对于每个方框，RPN预测两件事：

预测锚是对象的概率；

用于边界框回归器调整锚点以更好地适合物体的形状；

在有了不同形状和大小的边界框后，将其传递到RoI池层。对每个提案并对其进行裁剪，以便每个提案都包含一个对象。这就是RoI池层所做的事情，它为每个方框提取固定大小的特征图：

然后将这些特征图传递到全连接层，该层具有softmax和线性回归层，最终对对象进行分类并预测已识别对象的边界框。

4.2Faster RCNN的问题

上述讨论过的所有对象检测算法都使用区域来识别对象，且网络不会一次查看完整图像，而是按顺序关注图像的某些部分，这样会带来两个复杂性的问题：

该算法需要多次通过单个图像来提取到所有对象；

由于不是端到端的算法，不同的系统一个接一个地工作，整体系统的性能进一步取决于先前系统的表现效果。

链接： https://www.jianshu.com/p/51fc039ae7a4

4. 找零钱问题的贪心算法

问题描述：
当前有面值分别为2角5分，1角，5分，1分的硬币，请给出找n分钱的最佳方案（要求找出的硬币数目最少）
问题分析：
根据常识，我们到店里买东西找钱时，老板总是先给我们最大面值的，要是不够再找面值小一点的，直到找满为止。如果老板都给你找分数的或者几角的，那你肯定不干，另外，他也可能没有那么多零碎的钱给你找。其实这就是一个典型的贪心选择问题。
问题的算法设计与实现：
先举个例子，假如老板要找给我99分钱，他有上面的面值分别为25，10，5，1的硬币数，为了找给我最少的硬币数，那么他是不是该这样找呢，先看看该找多少个25分的， 99／25＝3，好像是3个，要是4个的话，我们还得再给老板一个1分的，我不干，那么老板只能给我3个25分，由于还少给我24，所以还得给我2个10分的和4个1分。
具体实现
//找零钱算法
//By falcon
//输入：数组m，依次存放从大到小排列的面值数，n为需要找的钱数，单位全部为分
//输出：数组num，对照数组m中的面值存放不同面值的硬币的个数，即找钱方案

5. 常见算法5、广度优先搜索 Breadth-First Search

1、定义

广度优先搜索 （Breadth-First Search）是最简便的图的搜索算法之一，又称 宽度优先搜索 ，这一算法也是很多重要的图算法的原型。广度优先搜索属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

2、应用

广度优先搜索被用于解决 最短路径问题（shortest-path problem） 。

广度优先搜索让你能够找出两样东西之间的最短距离，不过最短距离的含义有很多！使用广度优先搜索可以：

3、图简介

既然广度优先搜索是作用于图的一种算法，这里对图作一个简单的介绍，先不深入了解。

图由 节点 和 边 组成。一个节点可能与多个节点相连，这些节点被称为邻居。

广度优先算法的核心思想是：从初始节点开始，应用算符生成第一层节点，检查目标节点是否在这些后继节点中，若没有，再用产生式规则将所有第一层的节点逐一扩展，得到第二层节点，并逐一检查第二层节点中是否包含目标节点。若没有，再用算符逐一扩展第二层的所有节点……，如此依次扩展，检查下去，直到发现目标节点为止。即

广度优先搜索使用队列（queue）来实现，整个过程也可以看做一个倒立的树形。

例：假如你需要在你的人际关系网中寻找是否有职业为医生的人，图如下：

而使用广度优先搜索工作原理大概如下 ：

1、Python 3 ：

2、php ：

1、《算法图解》 https://www.manning.com/books/grokking-algorithms
2、SplQueue类： https://www.php.net/manual/zh/class.splqueue.php

6. 几种常见的查找算法之比较

二分法平均查找效率是O(logn)，但是需要数组是排序的。如果没有排过序，就只好先用O（nlogn)的预处理为它排个序了。而且它的插入比较困难，经常需要移动整个数组，所以动态的情况下比较慢。

哈希查找理想的插入和查找效率是O(1)，但条件是需要找到一个良好的散列函数，使得分配较为平均。另外，哈希表需要较大的空间，至少要比O(n)大几倍，否则产生冲突的概率很高。

二叉排序树查找也是O(logn)的，关键是插入值时需要做一些处理使得它较为平衡（否则容易出现轻重的不平衡，查找效率最坏会降到O(n)），而且写起来稍微麻烦一些，具体的算法你可以随便找一本介绍数据结构的书看看。当然，如果你用的是c语言，直接利用它的库类型map、multimap就可以了,它是用红黑树实现的，理论上插入、查找时间都是O(logn)，很方便，不过一般会比自己实现的二叉平衡树稍微慢一些。