亲宝软件园·资讯

展开

【摩天大楼平地起】基础篇 09 简述N种查找算法

nontracey 人气:0

引言

  在开始之前首先可以先思考一下假如没有查找算法会是什么情况?所有数据结构都需要全部遍历一遍,每次都一遍又一遍的查,从本质而言查找算法就是为了提高效率。

  经过前人一代又一代的努力,目前的查找算法大致可以分为静态查找和动态查找。从名字上就很容易理解,静态查找通俗而言就是查找的时候数据不变,而动态查找也可以理解为查找的时候数据发生了改变。

  所以这就衍生了个推论,即静态查找和动态查找算法不能通用,或者说在静态算法中使用动态算法不划算。

  还可以从顺序的维度来划分,可以划分为无序查找和有序查找。当然其中的顺序是相对的,也就是说是依据某个参照物来比是有序或者无序。

  平时大多数开发人员所编写的代码基本都是顺序查找,也就是说O(n)操作。

  接下去就让我们站在前人的肩膀上,改进一下我们的思路吧。

二分查找

  二分查找,平时在工作中应该或多或少都有听说过,这也算是除了顺序查找以外,最容易想到的查找算法了。

  核心思路就是不断的除2,直到找到为止,就类似于以前电视节目里面的猜价格,每次猜中间的值。

  但是这个算法前提就是给定的数据必须是有序的,如果无序的话,就没有办法决定是选上半截的中间值或是选下半截的中间值了。

  在这里贴上一张与顺序查找的对比图:

  

  代码实现:

  

 1  public class BinarySearch
 2     {
 3         public static int Demo(List<int> data, int key)
 4         {
 5             int low = 0, mid = 0;
 6             int high = data.Count - 1;
 7             while (low <= high)
 8             {
 9                 mid = (low + high) / 2;
10                 if (data[mid] == key)
11                 {
12                     return mid;
13                 }
14                 else if (data[mid] > key)
15                 {
16                     high = mid - 1;
17                 }
18                 else if (data[mid] < key)
19                 {
20                     low = mid + 1;
21                 }
22             }
23             return -1;
24         }
25     }
BinarySearch

 

  使用场景:

  .net已经提供的二分实现:BinarySearch

  二分法适用于数据较为连续较为均匀的,如内存地址,索引等

  算法复杂度 O(logn)

斐波那契查找

  提到斐波那契,具有大学经历的小伙伴一定不会陌生,第一反应肯定就是斐波那契数列,而斐波那契查找可能有些小伙伴就没有听过了。

  其实这个查找就是利用了斐波那契的黄金比例来减少分的次数。可以理解为是二分法的一个优化。

  ps:没有找到gif,来个png先顶上(捂脸)

  

  从图中可以看到斐波那契查找改变的是如何切分数据的问题。

  代码如下:

 1  public class FibonacciSearch
 2     {
 3         public static int Demo(List<int> data, int key)
 4         {
 5             int low = 0;
 6             int high = data.Count - 1; 
 7             
 8 
 9             var myFibonacciSearch = new List<int>(new int[40]);
10             myFibonacciSearch[0] = 0;
11             myFibonacciSearch[1] = 1;
12             for (int i = 2; i < myFibonacciSearch.Count; ++i)
13             {
14                 myFibonacciSearch[i] = myFibonacciSearch[i - 1] + myFibonacciSearch[i - 2];
15             }
16 
17             int relativePosition = 0;
18             while (data.Count > myFibonacciSearch[relativePosition] - 1)
19             {
20                 ++relativePosition;
21             }
22             int[] temp = new int[myFibonacciSearch[relativePosition] - 1];
23             data.CopyTo(temp);
24 
25             for (int i = data.Count; i < myFibonacciSearch[relativePosition] - 1; ++i)
26             {
27                 temp[i] = data[data.Count - 1];
28             }
29 
30             while (low <= high)
31             {
32                 int mid = low + myFibonacciSearch[relativePosition - 1] - 1;
33                 if (key < temp[mid])
34                 {
35                     high = mid - 1;
36                     relativePosition -= 1;
37                 }
38                 else if (key > temp[mid])
39                 {
40                     low = mid + 1;
41                     relativePosition -= 2;
42                 }
43                 else
44                 {
45                     if (mid < data.Count)
46                     {
47                         return mid;
48                     }
49                     else
50                     {
51                         return data.Count - 1;
52                     }
53                 }
54             }
55             return -1;
56         }
57     }
FibonacciSearch

  算法复杂度 O(logn)

 

插值查找

  这个可能一般的小伙伴没有听过这个查找算法,其实这个算法也是定义了如何去找。

  可以类比为查找字典的时候我们找X开头的单词总是会从后面开始找而找B开头的则会从头开始找。

  插值查找就是定义了这么一个规则,通过公式    搜索键值 = left + parseInt( ( key - data[left] ) / ( data[right] - data[left] ) )*( right - left ) )

  然后不停的切分,直到找到所需要的内容。

 

  下面附上维基百科里提供的JS程序段,感兴趣的可以翻译为自己常用的语言。

  

 1 var interpolationSearch = function(data, key){
 2     var left = 0;
 3     var right = data.length - 1;
 4     var m = 0;
 5     while(left <= right){
 6         var m = parseInt((right - left)*(key - data[left])/(data[right] - data[left])) + left;
 7         if( m < left || m > right)
 8             break;
 9         if(key < data[m])
10             right = m - 1;
11         else if(key > data[m])
12             left = m + 1;
13         else
14             return m;            
15     }
16     return -1;
17 };
18 
19 //執行
20 var data = getRandomData();
21 quickSort(data, 0, data.length-1);
22 interpolationSearch(data, 5);        // (data, key)
interpolationSearch

 

分块查找

  顺序查找的增强版,有点桶排序的味道。

  分开查找的要求就是分成N块每块内部可以无序但是块与块之间必须有序。

  这个就可以利用cpu的并行并发进行查找加速。

  如下图所示:

  

 

  

 

 哈希查找

  哈希对于各位开发小伙伴一定不陌生,哈希查找目的也很简单就是用空间来换时间。

  1)       用给定的哈希函数构造哈希表;

  2)       根据选择的冲突处理方法解决地址冲突;

  3)       在哈希表的基础上执行哈希查找。

  实用场景也很多:

  1.文件查找 

    比如百度网盘秒传功能,适用诸如sha256等哈希算法就可以快速的找到文件是否存在(md5冲突率相对较高,不适合用做文件判重)

  2.网络通信(微信消息算法)

    数据中组装一个随机的int值然后再组装所需要的参数如id 组装成long,即后半截有序前半截随机,再使用基数对比法,只对比后部分。最终实现数据不重复的情况下查找id

    用图解释就是 

    

 

    有点类似于雪花算法的感觉。

 

 树查找

  .net提供了教科书式的用法 感兴趣可以自行查看core源码中的SortedDictionary

  二叉树的查询性能还行,平均查询是O(Logn),但是最坏的情况会退化为O(n),在二叉树的基础上,

  又出来什么AVL,2-3-4,2-3(就是红黑,准确说 红黑树是2-3树的简单高效的实现)等等.

  而B/B+平衡树其实是2-3查找树的扩展,在文件系统中好用. 所以树而言,只管用,你自己的实现根本跟不上大佬们的性能.

  

加载全部内容

相关教程
猜你喜欢
用户评论