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