4.2. 常用算法¶
4.2.1. 排序、查找算法¶
选择排序¶
《Java中的经典算法之选择排序(SelectionSort)》
每一趟从待排序的记录中选出最小的元素,顺序放在已排好序的序列最后,直到全部记录排序完毕。
冒泡排序¶
-
相邻元素前后交换、把最大的排到最后。
时间复杂度 O(n²)
插入排序¶
快速排序¶
-
一侧比另外一侧都大或小。
归并排序¶
-
分而治之,分成小份排序,在合并(重建一个新空间进行复制)。
希尔排序¶
TODO
堆排序¶
-
排序过程就是构建最大堆的过程,最大堆:每个结点的值都大于或等于其左右孩子结点的值,堆顶元素是最大值。
计数排序¶
-
和桶排序过程比较像,差别在于桶的数量。
桶排序¶
-
桶排序将[0,1)区间划分为n个相同的大小的子区间,这些子区间被称为桶。
每个桶单独进行排序,然后再遍历每个桶。
基数排序¶
按照个位、十位、百位、…依次来排。
二分查找¶
-
要求待查找的序列有序。
时间复杂度 O(logN)。
-
while + 递归。
Java 中的排序工具¶
《Arrays.sort和Collections.sort实现原理解析》
Collections.sort算法调用的是合并排序。
Arrays.sort() 采用了2种排序算法 – 基本类型数据使用快速排序法,对象数组使用归并排序。
4.2.2. 布隆过滤器¶
常用于大数据的排重,比如email,url 等。 核心原理:将每条数据通过计算产生一个指纹(一个字节或多个字节,但一定比原始数据要少很多),其中每一位都是通过随机计算获得,在将指纹映射到一个大的按位存储的空间中。注意:会有一定的错误率。 优点:空间和时间效率都很高。 缺点:随着存入的元素数量增加,误算率随之增加。
-
基于 Redis 的 Bitmap 数据结构。
《网络爬虫:URL去重策略之布隆过滤器(BloomFilter)的使用》
使用Java中的 BitSet 类 和 加权和hash算法。
4.2.3. 字符串比较¶
KMP 算法¶
KMP:Knuth-Morris-Pratt算法(简称KMP) 核心原理是利用一个“部分匹配表”,跳过已经匹配过的元素。
4.2.4. 深度优先、广度优先¶
4.2.5. 贪心算法¶
4.2.6. 回溯算法¶
4.2.7. 剪枝算法¶
4.2.8. 动态规划¶
4.2.9. 朴素贝叶斯¶
-
P(B|A)=P(A|B)P(B)/P(A)