它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。 这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。
实现代码
随机找出一个数，可以随机取，也可以取固定位置，一般是取第一个或最后一个称为基准，然后就是比基准小的在左边，比基准大的放到右边，如何放做，就是和基准进行交换，这样交换完左边都是比基准小的，右边都是比较基准大的，这样就将一个数组分成了两个子数组，然后再按照同样的方法把子数组再分成更小的子数组，直到不能分解为止。
实现代码
归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
假设我们从一个海洋球池子里(很大的池子 不知道有多少个球 用N表示未知的个数)随机取出m颗作为抽样。请问如何在只遍历一次(O(N))的情况下，能够随机取出m个不重复的数据，且每颗球被抽样的概率相同。
这个场景强调了3件事：
- 海洋球有很多，所以不能一次性存入内存。
- 时间复杂度为O(N)。
- 随机选取m个数，每个数被选中的概率为m/N。
第1点限制了不能直接取N内的m个随机数，然后按索引取出数据。
第2点限制了不能先遍历一遍，然后分块存储数据，再随机选取。
第3点是数据选取绝对随机的保证。
实现代码
取样数据 m = 10
- 假设N<=10， 所有数据放入抽样池，每个球被抽中的概率为1
- 假设N==11, 前10颗球全部放入池中，概率都为1，第11颗球只需要在(1,11)获取随机数的时候取值1-10就行，所以最后一颗球进入池子的概率为10/11. 第一颗球被第11颗球替换掉的概率为 10/11 * 1/10 = 1/11 (首先第11颗球进入池子的概率是10/11,进入池子后抽到1的概率为1/10),所以第一颗球被抽样的概率为 1-1/11 = 10/11,满足m/N 的概率，同理可以知道前十颗球的概率都为m/N.
- 假设N==12, 第十二颗球想要进入池子，只需要在1-12之间随机数在1-10之间就可以，所以概率为10/12,满足m/N的概率。 第11颗球进入池子的概率为10/11, 进入池子之后被第十二颗球替换掉的概率为 10/12 * 1/10 = 1/12. 所以第十一颗球能够留在池子里的概率为 10/11 * (1 - 1/12) = 10/12 也满足 m/N的概率。
LRU全称是Least Recently Used，即最近最久未使用的意思。 LRU算法的设计原则是：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。
利用链表和hashmap。当需要插入新的数据项的时候，如果新数据项在链表中存在（一般称为命中），则把该节点移到链表头部，如果不存在，则新建一个节点，放到链表头部，存储后返回的节点地址作为map的value,若缓存满了，则把链表最后一个节点删除即可。在访问数据的时候，如果数据项在链表中存在，则把该节点移到链表头部，否则返回-1。这样一来在链表尾部的节点就是最近最久未访问的数据项。
Two queues算法类似于LRU-2，不同点在于2Q将LRU-2中的访问历史队列（注意这不是缓存数据的）改为一个FIFO缓存队列，即2Q算法=一个是FIFO队列，一个是LRU队列。命中率高于LRU
当数据第一次访问时，2Q算法将数据缓存在FIFO队列里面，当数据第二次被访问时，则将数据从FIFO队列移到LRU队列里，两个队列各自按照自己的方法淘汰数据。
-
新访问的数据插入到FIFO队列；
-
如果数据在FIFO队列中一直没有被再次访问，则最终按照FIFO规则淘汰；
-
如果数据在FIFO队列中被再次访问，则将数据移到LRU队列头部；
-
如果数据在LRU队列再次被访问，则将数据移到LRU队列头部；
-
LRU队列淘汰末尾的数据。
- 单调性(Monotonicity)，单调性是指如果已经有一些请求通过哈希分派到了相应的服务器进行处理，又有新的服务器加入到系统中时候，应保证原有的请求可以被映射到原有的或者新的服务器中去，而不会被映射到原来的其它服务器上去。 这个通过上面新增服务器ip5可以证明，新增ip5后，原来被ip1处理的user6现在还是被ip1处理，原来被ip1处理的user5现在被新增的ip5处理。
- 分散性(Spread)：分布式环境中，客户端请求时候可能不知道所有服务器的存在，可能只知道其中一部分服务器，在客户端看来他看到的部分服务器会形成一个完整的hash环。如果多个客户端都把部分服务器作为一个完整hash环，那么可能会导致，同一个用户的请求被路由到不同的服务器进行处理。这种情况显然是应该避免的，因为它不能保证同一个用户的请求落到同一个服务器。所谓分散性是指上述情况发生的严重程度。好的哈希算法应尽量避免尽量降低分散性。 一致性hash具有很低的分散性
- 平衡性(Balance)：平衡性也就是说负载均衡，是指客户端hash后的请求应该能够分散到不同的服务器上去。一致性hash可以做到每个服务器都进行处理请求，但是不能保证每个服务器处理的请求的数量大致相同，如下图
实现代码
核心思想，利用已经对比过的数据，回溯模式串，主串只向前。
核心方法Next(),获取当前字符串匹配失败后模式串(需要查找的串)回溯的位置。每个next值由前一位决定。
第一位为-1，当模式串回溯到-1位置时，主串指针需要往后移动，其他情况只回溯模式串到对应位置。
例如：
模式串 a b a b a a b b
回溯位置 -1 0 0 1 2 3 1 2
- 当第0位
a与主串不匹配时，next值为-1，主串指针后移，也就是模式串的第0位需要与主串的第一位进行对比 - 当第1位
b与主串不匹配时，next值为0，主串指针不变，模式串从第0位开始匹配主串 - 当第5位
a与主串不匹配时，next值为3，主串指针不变，模式串从第3(b)位开始匹配,如果到第五位才发现不匹配，说明前面是跟主串匹配的，也就是aba这个子串是匹配的，直接从位置3开始继续匹配。
雪花算法核心 1位符号位 41位时间戳 10位节点 12位序列号
- 41位时间戳表示毫秒，换算成年大约69年，从1970年开始，大约用到2039年 所以Twitter设计算法时设置了一个初始时间戳2006-03-21:20:50:14 GMT,所以此算法大约可以用到2075年
- 10位节点 总共可表示1024个节点
- 12位序列号 可以允许在统一毫秒内产生4096个id
单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始；链表是使用指针进行构造的列表；又称为结点列表，因为链表是由一个个结点组装起来的；其中每个结点都有指针成员变量指向列表中的下一个结点； 列表是由结点构成，head指针指向第一个成为表头结点，而终止于最后一个指向nuLL的指针。 单向链表包含两个域，一个是信息域，一个是指针域。也就是单向链表的节点被分成两部分，一部分是保存或显示关于节点的信息，第二部分存储下一个节点的地址，而最后一个节点则指向一个空值。
- 定义节点
- 定义链表，链表只有一个Head节点
- 创建一个值域为0，指针域指向nil的节点作为头部节点
- 新建节点的指针域都指向nil，循环链表，找到最后一个节点，并把指针域指向当前新建的节点（Append）
不使用第三个变量交换两个变量值的四种方法
- 算数运算
- 指针地址
- 位运算
- 栈
实现代码
杨辉三角，是二项式系数在三角形中的一种几何排列，中国南宋数学家杨辉1261年所著的《详解九章算法》一书中出现。在欧洲，帕斯卡（1623----1662）在1654年发现这一规律，所以这个表又叫做帕斯卡三角形。帕斯卡的发现比杨辉要迟393年，比贾宪迟600年。