查找算法总结
1五种查找算法总结
一、顺序查找条件：无序或有序队列。
原理：按顺序比较每个元素，直到找到关键字为止。
时间复杂度：O(n)
二、二分查找（折半查找）条件：有序数组
原理：查找过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。
如果在某一步骤数组为空，则代表找不到。
这种搜索算法每一次比较都使搜索范围缩小一半。
时间复杂度：O(logn)
三、二叉排序树查找条件：先创建二叉排序树：
1.若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2.若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3.它的左、右子树也分别为二叉排序树。
原理：
在二叉查找树b中查找x的过程为：
1.若b是空树，则搜索失败，否则：
2.若x等于b的根节点的数据域之值，则查找成功；否则：
3.若x小于b的根节点的数据域之值，则搜索左子树；否则：
4.查找右子树。
时间复杂度：
四、哈希表法（散列表）条件：先创建哈希表（散列表）
原理：根据键值方式(Keyvalue)进行查找，通过散列函数，定位数据元素。
时间复杂度：几乎是O(1)，取决于产生冲突的多少。
五、分块查找原理：将n个数据元素
每一块中的结点不必有序，但块与块之间必须**而第2块中任一元素又都必须小于第3块中的任一元素，……。
然后使用二分查找及顺序查找。
2查找算法的简单总结
在计算机许多应用领域中，查找操作都是十分重要的研究技术。查找效率的好坏直接影响应用软件的性能，而查找算法又分静态查找和动态查找。
静态查找:数据集合稳定，不需要添加，删除元素的查找操作。
动态查找:数据集合在查找的过程中需要添加或删除元素。
顺序查找:大家都知道，最简单的查找方法就是顺序查找 (一个接一个得查下去)。这种线性结构的查找效率是最低的，时间复杂度在O(N)数量级，最坏的情况莫过于所有数据都
找遍了，还是没找到。
或许你会想到不一定每个数据都要找一次。
折半查找就是一个不错的例子，对有序的线性数据进行查找，每一次都找1/2的部分，查找的次数当然就大大减少了。时间复杂度在O(log2 N)数量级上。
但是如果某些特定的数据一年可能才查找几次，而有些数据一天可能都要查找几百次，这种折半查找效率又不行了
那就针对被查找的概率构建数据结构吧
静态最优查找树/次优查找树:次优查找树的思想就是在折半查找二叉树的基础上求解一个带权(数据概率)路径长度最小/近视最小的树。总体上说，静态最优/次优查找树的时间复
杂度也在 O(log2 N)数量级上(特别是在数据具有查找概率的情况下也能保证这个效率)
此外，还有一些别的静态查找结构:索引顺序表的分块查找，线性冲突再散列的hash表的查找等等。
上面介绍查找表都属于静态查找结构，也就是说当需要查找的数据集合动态变化的时候，这些结构都很不方便。 比如:折半查找: 当查找过程中没有发现元素A的时候，需要动态
添加元素A，此时整个有序表将面临重新排序的问题。
静态最优查找树: 新增元素不光要重新排序，而且原有的整棵带权路径长度最小值的树也将重建(最优解变化了)。这在代价上是沉重的，这也是为什么 静态最优查找树并不适
合实际应用的巨大缺陷了。
正是由于实际应用中，很多时候需要在查找的同时进行添加，删除操作。因此便捷的动态查找结构就十分的重要了，例如:二叉查找树，平衡二叉树，红黑树，B-树/B+树。
二叉查找树:查找一个数不必遍历所有结点数据，查找效率很高。但是最坏情况下，二叉查找树蜕变成一个单支数，树的深度为n，其查找时间复杂度与顺序查找一样O(N)。最好的
情况是二叉排序树的形态和折半查找的判定树相同，其平均查找长度和log2(N)成正比 (O(log2(n)))。
效率总结 : 查找最好时间复杂度O(logN)，最坏时间复杂度O(N)。
插入删除操作算法简单，时间复杂度与查找差不多
所以平衡查找树就解决了二叉查找树不平衡的问题
平衡二叉树:又称 AVL树。 它除了具备二叉查找树的基本特征之外，还具有一个非常重要的特点:它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值(
平衡因子 ) 不超过1。也就是说AVL树每个节点的平衡因子只可能是-1、0和1(左子树高度减去右子树高度)。AVL保持平衡的基本思想就是在插入一个数据节点时，首先检查是否
破坏了平衡，若破坏，则找出其中的最小不平衡二叉树，在保持二叉排序树特性的情况下，调整最小不平衡子树中节点之间的关系，以达到新的平衡。所谓最小不平衡子树 指离插
入节点最近且以平衡因子的绝对值大于1的节点作为根的子树。 这里调整的方法就是4钟旋转方法，根据不同的情况进行调整。平衡二叉树的优势在于不会出现普通二叉查找树的最
差情况。其查找的时间复杂度为O(logN)。但是为了保证高度平衡，动态插入和删除的代价也随之增加，其查找代价也与树高密切相关，还有就是在大量数据情况下，所有二叉查找
结构都不适合，因为将比如几G数据在内存中组织成一棵平衡二叉树基本不可能。
效率总结 : 查找的时间复杂度维持在O(logN)，不会出现最差情况
AVL树在执行每个插入操作时最多需要1次旋转，其时间复杂度在O(logN)左右。
AVL树在执行删除时代价稍大，执行每个删除操作的时间复杂度需要O(2logN)。
正是上面提到的缺点，就有了深度有界查找树来解决。
红黑树:由于红黑树的一些性质就决定了红黑树的查找长度最多不超过2log(n+1)，因此其查找时间复杂度也是O(log N)级别的。每一个红黑树也是一个特化的二叉查找树，因此红
黑树上的查找操作与普通二叉查找树上的查找操作相同。 然而，在红黑树上进行插入操作和删除操作会导致不 再符合红黑树的性质。恢复红黑树的属性需要少量(O(log n))的颜
色变更(实际是非常快速的)和不超过三次树旋转(对于插入操作是两次)。 虽然插入和删除很复杂，但操作时间仍可以保持为 O(log n) 次，所以红黑树的优势很明显。
效率总结 : 查找效率最好情况下时间复杂度为O(logN)，但在最坏情况下比AVL要差一些，但也远远好于BST。
插入和删除操作改变树的平衡性的概率要远远小于AVL(RBT不是高度平衡的)。因此需要的旋转操作的可能性要小，而且一旦需要旋转，插入一个结点最多只需要旋转
2次，删除最多只需要旋转3次(小于AVL的删除操作所需要的旋转次数)。虽然变色操作的时间复杂度在O(logN)，但是实际上，这种操作由于简单所需要的代价很小。
上面总结的都是典型的二叉查找树结构，其查找的时间复杂度与树高相关。那么降低树高自然对查找效率是有所帮助的。另外还有一个比较实际的问题:就是大量数据存储中，实
现查询这样一个实际背景下，平衡二叉树由于树深度过大而造成磁盘IO读写过于频繁，进而导致效率低下。进而提出了多路查找树
平衡多路查找树:其性质就不在介绍了，主要思想就是每个节点存储多个元素，但是不是无限多，不然就成了节点内部的线性查找了，另外就是采用多叉树。一棵m阶的平衡多路查
找树和平衡二叉树不同的是，每次插入一个关键字并不是在树中上添加一个节点，而是首先在最低层的某个非终端结点中添加一个关键字，若该结点的关键字个数不超过m-1，则插
入完成。否则，要产生结点的分裂 。
效率总结: 由于考虑磁盘储存结构，B树的查找、删除、插入的代价都远远要小于任何二叉结构树(读写磁盘次数的降低)
B+树:是应文件系统所需而产生的一种平衡多路查找树的变形树。B+树的叶子结点包含了所有待查询关键字，而非终节点只是作为叶子结点中最大(最小)关键字的索引。因此B+树
的非终结点没有文件内容所在物理存储的地址，而平衡多路查找树所有结点均有文件内容所在的磁盘物理地址。 这个特点是B+树的一个重要优势(B+树的磁盘读写代价更低，B+树
的查询效率更加稳定)所在。B+树在数据库，文件系统的索引结构中是十分常用的。
在应用背景下，特别是文件结构存储中。B+树的应用要更多，其效率也要比B~树好
上面介绍的几种动态查找树(二叉查找树(BST)，平衡二叉查找树(AVL)，红黑树(RBT)，B~/B+树(B-tree))都是动态结构，在删除，插入操作的时候，都不需要彻底重建原始的索
引树。最多就是执行一定量的旋转，变色操作来有限的改变树的形态。而这些操作所付出的代价都远远小于重建一棵树， 查找的时间复杂度大体维持在O(log(N))数量级上。可能
有些结构在最差的情况下效率将会下降很快，比如上面说的二叉查找树最坏的情况。
3排序及查找算法总结
算法:指完成一个任务所需要的具体步骤和方法。即给定初始状态或输入数据，能够得出所要求或期望的终止状态或输出数据。
排序分类:
交换排序法:冒泡排序、鸡尾酒排序、奇偶排序
选择排序法:选择排序、堆排序
插入排序法:插入排序、希尔排序
归并排序法:归并排序
非比较排序:基数排序、桶排序、计数排序
1、插入排序:
定义:有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序
种类:直接插入排序，折半插入排序，链表插入排序，Shell排序
插入算法(insertionsort):把要排序的数组分成两部分:第一部分包含了这个数组的所有元素，但将最后一个元素除外，而第二部分就只包含这一个元素。在第一部分排序后，再把这个最后元素插入到此刻已是有序的第一部分里的正确位置中。
思想:将n个元素的数列分为已有序和无序两个部分，如下所示:
2、冒泡排序:(口令:N个数字来排队，两两相邻小靠前，外层循环N-1，内层循环N-1-I如果要降序排序，只要把程序中的大于号换成小于号就行了)
定义:依次比较相邻的两个数，将小数放在前面，大数放在后面。即首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。
3、选择排序
有一组要排序的数，首先拿出第一个数，让这个数与其后的每一个数进行比较，若大于第一个数，再与其后的数进行比较，如果小于第一个数，则将这个数跟其后的数进行比较，以次类推，最后获得最小的数，并将这个数与第一个数交换位置。
4、快速排序:是所有排序算法中最高效的一种
它采用了分治(分治:把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并)的思想:先保证列表的前半部分都小于后半部分，然后分别对前半部分和后半部分排序，这样整个列表就有序了。这是一种先进的思想，也是它高效的原因。因为在排序算法中，算法的高效与否与列表中数字间的比较次数有直接的关系，而"保证列表的前半部分都小于后半部分"就使得前半部分的任何一个数从此以后都不再跟后半部分的数进行比较了，大大减少了数字间不必要的比较。
5、希尔排序:希尔排序(ShellSort)是插入排序的一种。
基本思想:
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后，取第二个增量d2
6、堆排序
1、首先新建一个空列表，作用与插入排序中的“有序列表”相同
2、找到数列中最大的数字，将其加在“有序列表”的末尾，并将其从原始列中删除
3、重复2号步骤，直至原数列为空。
7、归并排序
1、申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2、设定两个指针，最初位置分别为两个已经排序序列的起始位置
3、比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4、重复步骤3直到某一指针达到序列尾
5、将另一序列剩下的所有元素直接复制到合并序列尾
8、基数排序
将所有待比较数值(正整数)统一为同样的数位长度数位较短的数前面补零.然后从最个位开始依次进行一次排序，将个位数相同的数值分为一组，这样从最低位排序一直到最高位排序完成以后数列就变成一个有序序列。
9、交换排序
根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是:将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
查找种类
1、二分查找
二分查找要求:1.必须采用顺序存储结构2.必须按关键字大小有序排列。
它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如果x 二分查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。因此，二分查找特别适用于那种一经建立就很少改动、而又经常需要查找的线性表。
2、顺序查找
用待查关键字和线性表中各结点关键字逐个比较，直到找到关键字值相等的节点，即查找成功，或查完全表，而未找到关键字相等的结点，即为查找失败。
3、分块查找
分块查找综合了顺序查找和二分法查找的优点，既有动态结构，又适于快速查找。
将待查找文件等长的分为若干个子文件(最后一个子文件长度可能小)。子文件内的元素无序，但子文件之间有序，即第一个子文件的最高关键字小于第二个子文件的最高关键字，第二个子文件的最高关键字小于第三个子文件的最高关键字，依次类推。再建立一个索引表(文件)，文件中的每个元素含有各子文件的最高关键字和各子文件中第一个元素的地址(下标)，索引文件按关键字有序。
查找时，对索引表可以顺序查找或二分法查找，在块内只能顺序查找。
4、散列查找
在记录的存储位置和它的关键字之间建立一个确定的对应关系f这样查找k时只要根据这个对应关系f找到给定值k的像f(k)。
是根据关键码值直接进行访问的数据结构，也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。
5、快速查找
Arrays.sort这个方法封装了排序算法
6、折半查找
将数列按有序化(递增或递减)排列，查找过程中采用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一半。
折半查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。但是，折半查找的先决条件是查找表中的数据元素必须有序。
算法步骤描述:
step1首先确定整个查找区间的中间位置
mid=(left+right)/2
step2用待查关键字值与中间位置的关键字值进行比较;
若相等，则查找成功
若大于，则在后(右)半个区域继续进行折半查找
若小于，则在前(左)半个区域继续进行折半查找
Step3对确定的缩小区域再按折半公式，重复上述步骤。最后，得到结果:要么查找成功，要么查找失败。
折半查找的存储结构采用一维数组存放。
7、索引查找
在索引表和主表(即线性表的索引存储结构)上进行的查找。
索引查找的过程是:首先根据给定的索引值K1，在索引表上查找出索引值等于KI的索引项，以确定对应予表在主表中的开始位置和长度，然后再根据给定的关键字K2，茬对应的子表中查找出关键字等于K2的元素(结点)。
若在主表中的每个子表后都预留有空闲位置，则索引存储也便于进行插入和删除运算，因为其运算过程只涉及到索引表和相应的子表，只需要对相应子表中的元素进行比较和移动，与其它任何子表无关。