# 基本的数据结构
# 数组
数组和链表的区别：数组支持随机访问，根据下标随机访问的时间复杂度为O(1) 排好序的数组，二分查找的时间复杂度是O(logn)
使用场景：如果需要快速访问数据，很少或不插入和删除元素，就应该用数组
为什么大多数编程语言中，数组要从0开始编号，而不是从1开始呢？ 从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移（offset）”。前面也讲到，如果用a来表示数组的首地址，a[0]就是偏移为0的位置，也就是首地 址，a[k]就表示偏移k个type_size的位置，所以计算a[k]的内存地址只需要用这个公式： a[k]_address = base_address + k * type_size 但是，如果数组从1开始计数，那我们计算数组元素a[k]的内存地址就会变为： a[k]_address = base_address + (k-1)*type_size 对比两个公式，我们不难发现，从1开始编号，每次随机访问数组元素都多了一次减法运算，对于CPU来说，就是多了一次减法指令。 数组作为非常基础的数据结构，通过下标随机访问数组元素又是其非常基础的编程操作，效率的优化就要尽可能做到极致。所以为了减少一次减法操作，数组选 择了从0开始编号，而不是从1开始。
数组需要一块连续的内存空间来存储，对内存的要求比较高。如果我们申请一个100MB大小的数组，当内存中没有连续的、足够大的存储空间时，即便内存的剩余总可用空间大于100MB，仍然会申请失败
# 链表
而链表恰恰相反，它并不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用，所以如果我们申请的是100MB大小的链表，根本不会有问题。
使用场景：需要经常插入和删除元素的数据结构
# 单链表
链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。如图所示，我们把这个记录下个结点地址的指针叫作后继指针next。
┌━━━━┐┌━━━━┐ ┌━━━━┐┌━━━━┐
-->┃data ┃ next ┃ —> ┃ data ┃ next ┃ —> NULL
└━━━━┘└━━━━┘ └━━━━┘└━━━━┘
我们习惯性地把第一个结点叫作头结点，把最后一个结点叫作尾结点。其中，头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。而尾结点特殊的地方是:指针不是指向下一个结点，而是指向一个空地址NULL，表示这是链表上最后一个结点。
头结点的定义是有讲究的，一般来说头结点有两种定义形式，一种是直接以某个元素结点为头结点
一种是以一个虚拟的节点作为头结点，即我们常说的哨兵
哨兵节点的好处： 可以看到，定义了哨兵结点的链表逻辑上清楚了很多,不用每次插入元素都对头结点进行判空（if (head == null) {head = new Node(val);})，也统一了每一个结点的添加逻辑。
public class LinkedList {
int length = 0; // 链表长度，非必须，可不加
Node head = new Node(0); // 哨兵结点
public void addNode(int val) {
Node tmp = head;//哨兵节点的好处：不用每次插入元素都对头结点进行判空!
while (tmp.next != null) {
tmp.next = tmp;
}
tmp.next = new Node(val);
}
}
缺点：
链表要想随机访问第k个元素，就没有数组那么高效了。因为链表中的数据并非连续存储的，所以无法像数组那样，根据首地址和下标，通过寻址公式就能直接计算出对应的内存地址，而是需要根据指针一个结点一个结点地依次遍历，直到找到相应的结点。
你可以把链表想象成一个队伍，队伍中的每个人都只知道自己后面的人是谁，所以当我们希望知道排在第k位的人是谁的时候，我们就需要从第一个人开始，一个一个地往下数。所以，链表随机访问的性能没有数组好，需要O(n)的时间复杂度。
# 循环链表
循环链表也很简单。它跟单链表唯一的区别就在尾结点。我们知道，单链表的尾结点指针指向空地址，表示这就是最后 的结点了。而循环链表的尾结点指针是指向链表的头结点。从我画的循环链表图中，你应该可以看出来，它像一个环一样首尾相连，所以叫作“循环”链表。
# 双向链表
它支持两个方向，每个结点不止有一个后继指针next指向后面的结 点，还有一个前驱指针prev指向前面的结点。 双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。
优缺点： 虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性。 适合：删除、插入操作，时间复杂度O(1) 用空间换时间的设计思想。当内存空间充足的时候，如果我们更加追求代码的执行速度，我们就可以选择空间复杂度相对较高、但时间复杂度相对很低的算法或者数据结构。相反，如果内存比较紧缺，比如代码跑在手机或者单片机上，这个时候，就要反过来用时间换空间的设计思路。
# 什么是数据结构和算法
数据结构就是指一组数据的存储结构。 算法就是操作数据的一组方法。
怎么学习？ 搞懂它的由来（Why）、特性、适用的场景以及它能解决的问题
| 算法 | 递推关系式 (Recurrence relation) | 运行时间 | 备注 |
|---|---|---|---|
| 二分查找 | T(n)=T(n/2)+O(1) | O(nlogn) | |
| 二叉树遍历 | T(n)=2T(n/2)+O(1) | O(n) | 每个节点仅遍历一次 |
| 最优排序矩阵搜索 | T(n)=2T(n/2)+O(logn) | O(n) | |
| 桶、计数、基数 | T(n)=2T(n/2)+O(n) | O(nlogn) |
如何系统地学习算法？ - 力扣（LeetCode）的回答 - 知乎
https://www.zhihu.com/question/20588261/answer/776221336
# Github链接
剑指Offer题库：https://leetcode-cn.com/problemset/lcof/
LeetCodeSwift: 1200 Star: https://github.com/diwu/LeetCode-Solutions-in-Swift
3100Star : https://github.com/soapyigu/LeetCode-Swift.git
343 star : https://github.com/lexrus/LeetCode.swift.git
JavaScript版本解题仓库： https://github.com/azl397985856/leetcode
王争的仓库 https://github.com/wangzheng0822/algo
4700Star：C语言实现的算法 https://github.com/TheAlgorithms/C
LeetCode-Swift (opens new window)
# 具体要求
王争：学习重点：复杂度分析、10个数据结构（数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie树;10个算法:递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法）。
《剑指Offer》：二分查找、归并排序、快速排序
考察点（网友）：
- 八大排序，三大查找
- 常见树的形式与树的增删查改
- 图的遍历方式与最短路径算法
# 时间复杂度
T(n) = O(f(n)) T(n)我们已经讲过了，它表示代码执行的时间;n表示数据规模的大小;f(n)表示每行代码执行的次数总和。因为这是一个公 式，所以用f(n)来表示。公式中的O，表示代码的执行时间T(n)与f(n)表达式成正比。
//例子1：求和
int cal(int n)
{
int sum = 0;
int i = 1;
for (; i <= n; ++i)
{
}
sum = sum + i;
return sum;
}
//例子2
int cal(int n)
{
int sum = 0;
int i = 1;
int j = 1;
for (; i <= n; ++i)
{
for (; j <= n; ++j)
{
sum = sum + i*j;
}
}
}
第一个例子中的T(n) = O(2n+2)，第二个例子中
的T(n) = O(2n2+2n+3)。这就是大O时间复杂度表示法。大O时间复杂度实际上并不具体表示代码真正的执行 时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度(asymptotic time complexity)，简称时间复杂度。 当n很大时，你可以把它想象成10000、100000。而公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略。我们只需要记录一个最大量级就可以 了，如果用大O表示法表示刚讲的那两段代码的时间复杂度，就可以记为:T(n) = O(n); T(n) = O(n2)。
# 几种常见的多项式时间复杂度
# 1. O(1)
首先你必须明确一个概念，O(1)只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。比如这段代码，即便有3行，它的时间复杂度也是O(1)， 而不是O(3)。
int i = 8;
int j = 6;
int sum = i + j;
只要代码的执行时间不随n的增大而增长，这样代码的时间复杂度我们都记作O(1)。或者说，一般情况下，只要算法中不存在循环语句、递归语 句，即使有成千上万行的代码，其时间复杂度也是Ο(1)。
# 2. O(logn)、O(nlogn)
对数阶时间复杂度非常常见，同时也是最难分析的一种时间复杂度。我通过一个例子来说明一下。
i=1;
while (i <= n) {
i = i * 2;
}
根据我们前面讲的复杂度分析方法，第三行代码是循环执行次数最多的。所以，我们只要能计算出这行代码被执行了多少次，就能知道整段代码的时间复杂度。 从代码中可以看出，变量i的值从1开始取，每循环一次就乘以2。当大于n时，循环结束。还记得我们高中学过的等比数列吗?实际上，变量i的取值就是一个等比 数列。如果我把它一个一个列出来，就应该是这个样子的:
$$2^0、2^1、 2^2 ... 2^k … 2^x=n$$
所以，我们只要知道x值是多少，就知道这行代码执行的次数了。通过2x=n求解x这个问题我们想高中应该就学过了，我就不多说了。x=log2n，所以，这段代码的 时间复杂度就是O(log2n)。 现在，我把代码稍微改下，你再看看，这段代码的时间复杂度是多少?
i=1;
while (i <= n) {
} i = i * 3;
根据我刚刚讲的思路，很简单就能看出来，这段代码的时间复杂度为O(log3n)。
实际上，不管是以2为底、以3为底，还是以10为底，我们可以把所有对数阶的时间复杂度都记为O(logn)。为什么呢?
我们知道，对数之间是可以互相转换的，$log_3n$ 就等于$log_32$ * $log_2n$，所以O($log_3n$ ) = O(C * $log_2n$ )，其中C=$log_3 2$ 是一个常量。
基于我们前面的一个理论:在采用 大O标记复杂度的时候，可以忽略系数，即O(Cf(n)) = O(f(n))。所以，O(log2n) 就等于O(log3n)。
因此，在对数阶时间复杂度的表示方法里，我们忽略对数的“底”， 统一表示为O(logn)。
如果你理解了我前面讲的O(logn)，那O(nlogn)就很容易理解了。还记得我们刚讲的乘法法则吗?如果一段代码的时间复杂度是O(logn)，我们循环执行n遍，时间复 杂度就是O(nlogn)了。而且，O(nlogn)也是一种非常常见的算法时间复杂度。比如，归并排序、快速排序的时间复杂度都是O(nlogn)。
# 3. O(m+n)、O(m*n)
03|复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？ file:///F/temp/geektime/数据结构与算法之美/03复杂度分析（上）：如何分析、统计算法的执行效率和资源消耗？.html[2019/1/15 15:35:11] 我们再来讲一种跟前面都不一样的时间复杂度，代码的复杂度由两个数据的规模来决定。老规矩，先看代码！ int cal(int m, int n) { int sum_1 = 0; int i = 1; for (; i < m; ++i) { sum_1 = sum_1 + i; } int sum_2 = 0; int j = 1; for (; j < n; ++j) { sum_2 = sum_2 + j; } return sum_1 + sum_2; } 从代码中可以看出，m和n是表示两个数据规模。我们无法事先评估m和n谁的量级大，所以我们在表示复杂度的时候，就不能简单地利用加法法则，省略掉其中一 个。所以，上面代码的时间复杂度就是O(m+n)。 针对这种情况，原来的加法法则就不正确了，我们需要将加法规则改为：T1(m) + T2(n) = O(f(m) + g(n))
# 复杂度分析
最好情况时间复杂度（best case time complexity）、最坏情况时间复杂度（worst case time complexity）、平均情况时间复杂度（average case time complexity）、均摊时间复杂度（amortized time complexity）。
// n 表示数组 array 的长度
int find(int[] array, int n, int x) {
int i = 0;
int pos = -1;
for (; i < n; ++i) {
if (array[i] == x) {
pos = i;
break;
}
}
return pos;
}
最好情况时间复杂度就是，在最理想的情况下，执行这段代码的时间复杂度。就像我们刚刚讲到的，在最理想的情况下，要查找的变量 x 正好是数组的第一个元素，这个时候对应的时间复杂度就是最好情况时间复杂度。
同理，最坏情况时间复杂度就是，在最糟糕的情况下，执行这段代码的时间复杂度。就像刚举的那个例子，如果数组中没有要查找的变量 x，我们需要把整个数组都遍历一遍才行，所以这种最糟糕情况下对应的时间复杂度就是最坏情况时间复杂度。
# 基本的数据结构
# 数组
数组和链表的区别：数组支持随机访问，根据下标随机访问的时间复杂度为O(1) 排好序的数组，二分查找的时间复杂度是O(logn)
使用场景：如果需要快速访问数据，很少或不插入和删除元素，就应该用数组
为什么大多数编程语言中，数组要从0开始编号，而不是从1开始呢？ 从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移（offset）”。前面也讲到，如果用a来表示数组的首地址，a[0]就是偏移为0的位置，也就是首地 址，a[k]就表示偏移k个type_size的位置，所以计算a[k]的内存地址只需要用这个公式： a[k]_address = base_address + k * type_size 但是，如果数组从1开始计数，那我们计算数组元素a[k]的内存地址就会变为： a[k]_address = base_address + (k-1)*type_size 对比两个公式，我们不难发现，从1开始编号，每次随机访问数组元素都多了一次减法运算，对于CPU来说，就是多了一次减法指令。 数组作为非常基础的数据结构，通过下标随机访问数组元素又是其非常基础的编程操作，效率的优化就要尽可能做到极致。所以为了减少一次减法操作，数组选 择了从0开始编号，而不是从1开始。
数组需要一块连续的内存空间来存储，对内存的要求比较高。如果我们申请一个100MB大小的数组，当内存中没有连续的、足够大的存储空间时，即便内存的剩余总可用空间大于100MB，仍然会申请失败
# 链表
而链表恰恰相反，它并不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用，所以如果我们申请的是100MB大小的链表，根本不会有问题。
使用场景：需要经常插入和删除元素的数据结构
# 单链表
链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。如图所示，我们把这个记录下个结点地址的指针叫作后继指针next。
┌━━━━┐┌━━━━┐ ┌━━━━┐┌━━━━┐
-->┃data ┃ next ┃ —> ┃ data ┃ next ┃ —> NULL
└━━━━┘└━━━━┘ └━━━━┘└━━━━┘
我们习惯性地把第一个结点叫作头结点，把最后一个结点叫作尾结点。其中，头结点用来记录链表的基地址。有了它，我们就可以遍历得到整条链表。而尾结点特殊的地方是:指针不是指向下一个结点，而是指向一个空地址NULL，表示这是链表上最后一个结点。
头结点的定义是有讲究的，一般来说头结点有两种定义形式，一种是直接以某个元素结点为头结点
一种是以一个虚拟的节点作为头结点，即我们常说的哨兵
哨兵节点的好处： 可以看到，定义了哨兵结点的链表逻辑上清楚了很多,不用每次插入元素都对头结点进行判空（if (head == null) {head = new Node(val);})，也统一了每一个结点的添加逻辑。
public class LinkedList {
int length = 0; // 链表长度，非必须，可不加
Node head = new Node(0); // 哨兵结点
public void addNode(int val) {
Node tmp = head;//哨兵节点的好处：不用每次插入元素都对头结点进行判空!
while (tmp.next != null) {
tmp.next = tmp;
}
tmp.next = new Node(val);
}
}
缺点：
链表要想随机访问第k个元素，就没有数组那么高效了。因为链表中的数据并非连续存储的，所以无法像数组那样，根据首地址和下标，通过寻址公式就能直接计算出对应的内存地址，而是需要根据指针一个结点一个结点地依次遍历，直到找到相应的结点。
你可以把链表想象成一个队伍，队伍中的每个人都只知道自己后面的人是谁，所以当我们希望知道排在第k位的人是谁的时候，我们就需要从第一个人开始，一个一个地往下数。所以，链表随机访问的性能没有数组好，需要O(n)的时间复杂度。
# 循环链表
循环链表也很简单。它跟单链表唯一的区别就在尾结点。我们知道，单链表的尾结点指针指向空地址，表示这就是最后 的结点了。而循环链表的尾结点指针是指向链表的头结点。从我画的循环链表图中，你应该可以看出来，它像一个环一样首尾相连，所以叫作“循环”链表。
# 双向链表
它支持两个方向，每个结点不止有一个后继指针next指向后面的结 点，还有一个前驱指针prev指向前面的结点。 双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。
优缺点： 虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性。 适合：删除、插入操作，时间复杂度O(1) 用空间换时间的设计思想。当内存空间充足的时候，如果我们更加追求代码的执行速度，我们就可以选择空间复杂度相对较高、但时间复杂度相对很低的算法或者数据结构。相反，如果内存比较紧缺，比如代码跑在手机或者单片机上，这个时候，就要反过来用时间换空间的设计思路。
# 数组与链表
| 时间复杂度 | 数组 | 链表 |
|---|---|---|
| 插入、删除 | O(n) | O(1) |
| 随机访问（取第n个值） | O(1) | O(n) |
数组简单易用，在实现上使用的是连续的内存空间，可以借助CPU的缓存机制，预读数组中的数据，所以访问效率更高。而链表在内存中并不是连续存储，所以数组的缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致“内存不足(out of memory)”。如果声明的数组过小，则可能出现不够用的情况。这时只能再申请一个更大的内存空间，把原数组拷贝进去，非常费时。链表本身没有大小的限制， 天然地支持动态扩容，我觉得这也是它与数组最大的区别。 你可能会说，我们Java中的ArrayList容器，也可以支持动态扩容啊?我们上一节课讲过，当我们往支持动态扩容的数组中插入一个数据时，如果数组中没有空闲空 间了，就会申请一个更大的空间，将数据拷贝过去，而数据拷贝的操作是非常耗时的。 我举一个稍微极端的例子。如果我们用ArrayList存储了了1GB大小的数据，这个时候已经没有空闲空间了，当我们再插入数据的时候，ArrayList会申请一 个1.5GB大小的存储空间，并且把原来那1GB的数据拷贝到新申请的空间上。听起来是不是就很耗时? 除此之外，如果你的代码对内存的使用非常苛刻，那数组就更适合你。因为链表中的每个结点都需要消耗额外的存储空间去存储一份指向下一个结点的指针，所 以内存消耗会翻倍。而且，对链表进行频繁的插入、删除操作，还会导致频繁的内存申请和释放，容易造成内存碎片，如果是Java语言，就有可能会导致频繁的GC(Garbage Collection，垃圾回收)。
# 写链表
在结点p后面插入一个新的结点
new_node->next = p->next;
p->next = new_node;
向一个空链表中插入第一个结点
f (head == null) {
head = new_node;
}
删除结点p的后继结点 p->next = p->next->next; 删除链表中的最后一个结点 if (head->next == null) { head = null; }
####5个常见的链表操作
你只要把这几个操作都能写熟练，不熟就多写几遍，我保证你之后再也不会害怕写链表代码。
单链表反转 链表中环的检测 两个有序的链表合并 删除链表倒数第n个结点 求链表的中间结点
# LRU 缓存淘汰算法？
维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。
\1. 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
\2. 如果此数据没有在缓存链表中，又可以分为两种情况：
- 如果此时缓存未满，则将此结点直接插入到链表的头部；
- 如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。
这样我们就用链表实现了一个 LRU 缓存，是不是很简单？
# 队列
顺序队列和链式队列
我们知道了，队列跟栈一样，也是一种抽象的数据结构。它具有先进先出的特性，支持在队尾插入元素，在队头删除元素，那究竟该如何实现一个队列呢？
跟栈一样，队列可以用数组来实现，也可以用链表来实现。用数组实现的栈叫作顺序栈，用链表实现的栈叫作链式栈。同样，用数组实现的队列叫作**顺序队列，用链表实现的队列叫作链式队列**。
对于栈来说，我们只需要一个栈顶指针就可以了。但是队列需要两个指针：一个是 head 指针，指向队头；一个是 tail 指针，指向队尾。
出队dequeue时可以不用搬移数据。如果没有空闲空间了，我们只需要在入队时，再集中触发一次数据的搬移操作。借助这个思想，出队函数 dequeue() 保持不变，我们稍加改造一下入队函数 enqueue() 的实现，就可以轻松解决刚才的问题了。
// 入队操作，将 item 放入队尾
public boolean enqueue(String item) {
// tail == n 表示队列末尾没有空间了
if (tail == n) {
// tail ==n && head==0，表示整个队列都占满了
if (head == 0) return false;
// 数据搬移!!!
for (int i = head; i < tail; ++i) {
items[i-head] = items[i];
}
// 搬移完之后重新更新 head 和 tail
tail -= head;
head = 0;
}
items[tail] = item;
++tail;
return true;
}
# 循环队列
public class CircularQueue {
// 数组：items，数组大小：n
private String[] items;
private int n = 0;
// head 表示队头下标，tail 表示队尾下标
private int head = 0;
private int tail = 0;
// 申请一个大小为 capacity 的数组
public CircularQueue(int capacity) {
items = new String[capacity];
n = capacity;
}
// 入队
public boolean enqueue(String item) {
// 队列满了
if ((tail + 1) % n == head) return false;
items[tail] = item;
tail = (tail + 1) % n;
return true;
}
// 出队
public String dequeue() {
// 如果 head == tail 表示队列为空
if (head == tail) return null;
String ret = items[head];
head = (head + 1) % n;
return ret;
}
}
# 阻塞队列和并发队列
阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说，就是
在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；
如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。
基于阻塞队列可实现“生产者 - 消费者模型”，可以有效地协调生产和消费的速度。当“生产者”生产数据的速度过快，“消费者”来不及消费时，存储数据的队列很快就会满了。这个时候，生产者就阻塞等待，直到“消费者”消费了数据，“生产者”才会被唤醒继续“生产”。
# 线程池问题
CPU 资源是有限的，任务的处理速度与线程个数并不是线性正相关。相反，过多的线程反而会导致 CPU 频繁切换，处理性能下降。所以，线程池的大小一般都是综合考虑要处理任务的特点和硬件环境，来事先设置的。
当我们向固定大小的线程池中请求一个线程时，如果线程池中没有空闲资源了，这个时候线程池如何处理这个请求？是拒绝请求还是排队请求？各种处理策略又是怎么实现的呢？
我们一般有两种处理策略。
第一种是非阻塞的处理方式，直接拒绝任务请求；
另一种是阻塞的处理方式，将请求排队，等到有空闲线程时，取出排队的请求继续处理。那如何存储排队的请求呢？
我们希望公平地处理每个排队的请求，先进者先服务，所以队列这种数据结构很适合来存储排队请求。
基于链表的实现方式，可以实现一个支持无限排队的无界队列（unbounded queue），但是可能会导致过多的请求排队等待，请求处理的响应时间过长。所以，针对响应时间比较敏感的系统，基于链表实现的无限排队的线程池是不合适的。
而基于数组实现的有界队列（bounded queue），队列的大小有限，所以线程池中排队的请求超过队列大小时，接下来的请求就会被拒绝，这种方式对响应时间敏感的系统来说，就相对更加合理。不过，设置一个合理的队列大小，也是非常有讲究的。队列太大导致等待的请求太多，队列太小会导致无法充分利用系统资源、发挥最大性能。
除了前面讲到队列应用在线程池请求排队的场景之外，队列可以应用在任何有限资源池中，用于排队请求，比如数据库连接池等。实际上，对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队。
#递归：“最终推荐人”
去的过程叫“递”，回来的过程叫“归”
我的理解：递归方法或函数就是自己循环自己，通过套娃的方式把大问题分节成小问题
好处：高效、简洁
###递归需要满足的三个条件
1. 一个问题的解可以分解为几个子问题的解
2. 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
3. 存在递归终止条件
假如这里有 n 个台阶，每次你可以跨 1 个台阶或者 2 个台阶，请问走这 n 个台阶有多少种走法？
n 个台阶的走法 等价于：先走 1 阶后，剩下的n-1 个台阶的走法 + 先走 2 阶后，剩下的n-2 个台阶的走法。用公式表示就是：
f(n) = f(n-1)+f(n-2)
把递归终止条件和刚刚得到的递推公式放到一起就是这样的：
f(1) = 1;
f(2) = 2;
f(n) = f(n-1)+f(n-2)
有了这个公式，我们转化成递归代码就简单多了。最终的递归代码是这样的：
int f(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return f(n-1) + f(n-2);
}
如何避免出现堆栈溢出呢？
在代码中限制递归调用的最大深度
// 全局变量，表示递归的深度。
int depth = 0;
int f(int n) {
++depth；
if (depth > 1000) throw exception;
if (n == 1) return 1;
return f(n-1) + 1;
}
// 这种做法并不能完全解决问题，因为最大允许的递归深度跟当前线程剩余的栈空间大小有关，事先无法计算。如果实时计算，代码过于复杂，就会影响代码的可读性。所以，如果最大深度比较小，比如 10、50，就可以用这种方法，否则这种方法并不是很实用。
# 递归代码要警惕重复计算
想要计算 f(5)，需要先计算 f(4) 和 f(3)，而计算 f(4) 还需要计算 f(3)，因此，f(3) 就被计算了很多次，这就是重复计算问题。
为了避免重复计算，我们可以通过在一个数据结构（比如散列表）来保存已经求解过的 f(k)。当递归调用到 f(k) 时，先看下是否已经求解过了。如果是，则直接从散列表中取值返回，不需要重复计算，这样就能避免刚讲的问题了。
# 将递归代码改写为非递归代码
int f(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
int ret = 0;
int pre = 2;//前一个
int prepre = 1;//前前一个
for (int i = 3; i <= n; ++i) {
ret = pre + prepre;
prepre = pre;
pre = ret;
}
return ret;
}
//笼统地讲，所有的递归代码都可以改为这种**迭代循环**的非递归写法。
//因为递归本身就是借助栈来实现的，只不过我们使用的栈是系统或者虚拟机本身提供的，我们没有感知罢了。如果我们自己在内存堆上实现栈，手动模拟入栈、出栈过程，这样任何递归代码都可以改写成看上去不是递归代码的样子。
//但是这种思路实际上是将递归改为了“手动”递归，本质并没有变，而且也并没有解决前面讲到的某些问题，徒增了实现的复杂度。
# 排序算法
| 排序算法 | 时间复杂度 | 是否基于比较 | 备注 |
|---|---|---|---|
| 冒泡、插入、选择 | O(n2) | ✅ | 原地排序算法 空间复杂度是 O(1) |
| 快排、归并 | O(nlogn) | ✅ | |
| 桶、计数、基数 | O(n) | ❌ |
八大排序：
| 排序算法 | 时间复杂度 （平均、最好、最坏） | 空间复杂度 | 备注 | ||
|---|---|---|---|---|---|
| 插入 | O(n^2)、O(n)、O(n^2) | O(1) | ✔️ | ||
| Shell（希尔） | O(n^2)、O(n)、O(n^2) | O(1) | ❌ | ||
| 直接选择 | O(n^2)、O(n^2)、O(n^2) | O(1) | ❌ | ||
| 堆排序 | O(nlogn)、O(nlogn)、O(nlogn) | O(1) | ❌ | ||
| 冒泡排序 | O(n^2)、O(n)、O(n^2) | O(1) | ✔️ | ||
| 快速 | O(nlogn)、O(nlogn)、O(n^2) | O(nlogn) | ❌ | ||
| 归并 | O(nlogn)、O(nlogn)、O(nlogn) | O(1) | ✔️ | ||
| 基数 | O(d(r+n))、O(d(rd+n))、O(d(r+n)) | O(rd+n) | ✔️ |
# 如何评价和分析排序算法
####排序算法的执行效率
最好情况、最坏情况、平均情况时间复杂度
时间复杂度的系数、常数 、低阶
时间复杂度反应的是数据规模 n 很大的时候的一个增长趋势，所以它表示的时候会忽略系数、常数、低阶。但是实际的软件开发中，我们排序的可能是 10 个、100 个、1000 个这样规模很小的数据，所以，在对同一阶时间复杂度的排序算法性能对比的时候，我们就要把系数、常数、低阶也考虑进来。
比较次数和交换（或移动）次数 ####排序算法的内存消耗
原地排序算法，就是特指空间复杂度是 O(1) 的排序算法。
####排序算法的稳定性
如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。
比如我们有一组数据 2，9，3，4，8，3，按照大小排序之后就是 2，3，3，4，8，9。
这组数据里有两个 3。经过某种排序算法排序之后，如果两个 3 的前后顺序没有改变，那我们就把这种排序算法叫作稳定的排序算法；如果前后顺序发生变化，那对应的排序算法就叫作不稳定的排序算法。
# 冒泡排序（Bubble Sort）
Panda总结：
因为水里面的大气泡会上升的快 (opens new window)，所以从小到大排序的时候大的在后面，可以： 从左到右依次比较相邻的两个数据（前两个、第二个和第三个、第三个和第四个...），如果左边的大，就让这两个数据换下位置，让大的去后面，第一轮下来之后，最大的数字位于最后一个。
第二轮之后，第二大的数据位于倒数第二。重复类似的操作即可排序完成！
// 冒泡排序，a 表示数组，n 表示数组大小
public void bubbleSort(int[] a, int n) {
if (n <= 1) return;
for (int i = 0; i < n; ++i) {
// 提前退出冒泡循环的标志位
boolean flag = false;
for (int j = 0; j < n - i - 1; ++j) {
if (a[j] > a[j+1]) { // 交换
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
flag = true; // 表示有数据交换
}
}
if (!flag) break; // 没有数据交换，提前退出
}
}
有序度是数组中具有有序关系的元素对的个数（默认从小到大为有序）
Panda的理解：是左边比右边元素大的情况个数
对于一个倒序排列的数组，比如 6，5，4，3，2，1，有序度是 0；
对于一个完全有序的数组，比如 1，2，3，4，5，6，有序度就是n*(n-1)/2，也就是 15。我们把这种完全有序的数组的有序度叫作满有序度。
逆序度的定义正好跟有序度相反
# 插入排序（Insertion Sort）
核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。
Panda总结：首先假定第一个数字已经排序完成，然后依次拿第二个、第三个……数字跟左边的数字比较，如果比左边的小，就左移，直到所有的数字排序完成
# 归并排序
Panda总结：将N个数据从中间分成两部分，然后对两部分分别递归排序，再将排好序的两部分合并在一起，这样整个数组就都有序了（递归+合并=归并？）
递推公式：
merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))
终止条件：
p >= r 不用再继续分解
//merge_sort(p…r) 表示，给下标从 p 到 r 之间的数组排序。我们将这个排序问题转化为了两个子问题，merge_sort(p…q) 和 merge_sort(q+1…r)，其中下标 q 等于 p 和 r 的中间位置，也就是 (p+r)/2。当下标从 p 到 q 和从 q+1 到 r 这两个子数组都排好序之后，我们再将两个有序的子数组合并在一起，这样下标从 p 到 r 之间的数据就也排好序了。
// 归并排序算法伪代码, A 是数组，n 表示数组大小
merge_sort(A, n) {
merge_sort_c(A, 0, n-1)
}
// 递归调用函数
merge_sort_c(A, p, r) {
// 递归终止条件
if p >= r then return
// 取 p 到 r 之间的中间位置 q
q = (p+r) / 2
// 分治递归
merge_sort_c(A, p, q)
merge_sort_c(A, q+1, r)
// 将 A[p...q] 和 A[q+1...r] 合并为 A[p...r]
merge(A[p...r], A[p...q], A[q+1...r])
}
merge(A[p...r], A[p...q], A[q+1...r]) {
var i := p，j := q+1，k := 0 // 初始化变量 i, j, k
var tmp := new array[0...r-p] // 申请一个大小跟 A[p...r] 一样的临时数组
while i<=q AND j<=r do {
if A[i] <= A[j] {
tmp[k++] = A[i++] // i++ 等于 i:=i+1
} else {
tmp[k++] = A[j++]
}
}
// 判断哪个子数组中有剩余的数据
var start := i，end := q
if j<=r then start := j, end:=r
// 将剩余的数据拷贝到临时数组 tmp
while start <= end do {
tmp[k++] = A[start++]
}
// 将 tmp 中的数组拷贝回 A[p...r]
for i:=0 to r-p do {
A[p+i] = tmp[i]
}
}
归并排序的时间复杂度是多少？
归并排序涉及递归，时间复杂度的分析稍微有点复杂。我们正好借此机会来学习一下，如何分析递归代码的时间复杂度。
在递归那一节我们讲过，递归的适用场景是，一个问题 a 可以分解为多个子问题 b、c，那求解问题 a 就可以分解为求解问题 b、c。问题 b、c 解决之后，我们再把 b、c 的结果合并成 a 的结果。
如果我们定义求解问题 a 的时间是 T(a)，求解问题 b、c 的时间分别是 T(b) 和 T( c)，那我们就可以得到这样的递推关系式：
T(a) = T(b) + T(c) + K
其中 K 等于将两个子问题 b、c 的结果合并成问题 a 的结果所消耗的时间。
从刚刚的分析，我们可以得到一个重要的结论：不仅递归求解的问题可以写成递推公式，递归代码的时间复杂度也可以写成递推公式。
套用这个公式，我们来分析一下归并排序的时间复杂度。
我们假设对 n 个元素进行归并排序需要的时间是 T(n)，那分解成两个子数组排序的时间都是 T(n/2)。我们知道，merge() 函数合并两个有序子数组的时间复杂度是 O(n)。所以，套用前面的公式，归并排序的时间复杂度的计算公式就是：
T(1) = C； n=1 时，只需要常量级的执行时间，所以表示为 C。
T(n) = 2*T(n/2) + n； n>1
通过这个公式，如何来求解 T(n) 呢？还不够直观？那我们再进一步分解一下计算过程。
T(n) = 2*T(n/2) + n
= 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
= 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
= 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
......
= 2^k * T(n/2^k) + k * n
......
通过这样一步一步分解推导，我们可以得到 T(n) = 2^kT(n/2^k)+kn。当 T(n/2^k)=T(1) 时，也就是 n/2^k=1，我们得到 k=log2n 。我们将 k 值代入上面的公式，得到 T(n)=Cn+nlog2n 。如果我们用大 O 标记法来表示的话，T(n) 就等于 O(nlogn)。所以归并排序的时间复杂度是 O(nlogn)。
从我们的原理分析和伪代码可以看出，归并排序的执行效率与要排序的原始数组的有序程度无关，所以其时间复杂度是非常稳定的，不管是最好情况、最坏情况，还是平均情况，时间复杂度都是 O(nlogn)。
# 快速排序
# 快排的思想：
如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。
我们遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。经过这一步骤之后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot 的。
根据分治、递归的处理思想，我们可以用递归排序下标从 p 到 q-1 之间的数据和下标从 q+1 到 r 之间的数据，直到区间缩小为 1（每个区间都是一个数据了），就说明所有的数据都有序了。
如果我们用递推公式来将上面的过程写出来的话，就是这样：
//递推公式：
quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1, r)
//终止条件(这里的p、r不代表起始位置，而是代表一个小的区间起始)：
p >= r
我将递推公式转化成递归代码。跟归并排序一样，我还是用伪代码来实现，你可以翻译成你熟悉的任何语言。
// 快速排序，A 是数组，n 表示数组的大小
quick_sort(A, n) {
quick_sort_c(A, 0, n-1)
}
// 快速排序递归函数，p,r 为下标
quick_sort_c(A, p, r) {
if p >= r then return
q = partition(A, p, r) // 获取分区点
quick_sort_c(A, p, q-1)
quick_sort_c(A, q+1, r)
}
归并排序中有一个 merge() 合并函数，我们这里有一个 partition() 分区函数。partition() 分区函数实际上我们前面已经讲过了，就是随机选择一个元素作为 pivot（一般情况下，可以选择 p 到 r 区间的最后一个元素），然后对 A[p…r] 分区，函数返回 pivot 的下标。
如果我们不考虑空间消耗的话，partition() 分区函数可以写得非常简单。我们申请两个临时数组 X 和 Y，遍历 A[p…r]，将小于 pivot 的元素都拷贝到临时数组 X，将大于 pivot 的元素都拷贝到临时数组 Y，最后再将数组 X 和数组 Y 中数据顺序拷贝到 A[p…r]。
但是，如果按照这种思路实现的话，partition() 函数就需要很多额外的内存空间，所以快排就不是原地排序算法了。如果我们希望快排是原地排序算法，那它的空间复杂度得是 O(1)，那 partition() 分区函数就不能占用太多额外的内存空间，我们就需要在 A[p…r] 的原地完成分区操作。
原地分区函数的实现思路非常巧妙，我写成了伪代码，我们一起来看一下:
partition(A, p, r) {
pivot := A[r]
i := p
for j := p to r-1 do {
if A[j] < pivot {
swap A[i] with A[j]
i := i+1
}
}
swap A[i] with A[r]
return i
}
这里的处理有点类似选择排序。我们通过游标 i 把 A[p…r-1] 分成两部分。A[p…i-1] 的元素都是小于 pivot 的，我们暂且叫它“已处理区间”，A[i…r-1] 是“未处理区间”。我们每次都从未处理的区间 A[i…r-1] 中取一个元素 A[j]，与 pivot 对比，如果小于 pivot，则将其加入到已处理区间的尾部，也就是 A[i] 的位置。
数组的插入操作还记得吗？在数组某个位置插入元素，需要搬移数据，非常耗时。当时我们也讲了一种处理技巧，就是交换，在 O(1) 的时间复杂度内完成插入操作。这里我们也借助这个思想，只需要将 A[i] 与 A[j] 交换，就可以在 O(1) 时间复杂度内将 A[j] 放到下标为 i 的位置。
文字不如图直观，所以我画了一张图来展示分区的整个过程。
因为分区的过程涉及交换操作，如果数组中有两个相同的元素，比如序列 6，8，7，6，3，5，9，4，在经过第一次分区操作之后，两个 6 的相对先后顺序就会改变。所以，快速排序并不是一个稳定的排序算法。
# Panda总结：
快速排序是选取N个数据的某个值（比如取最后一个值x）作为临界点，小于x的放到左边（暂且叫它集合A），大于x的放到右边（集合B），然后对集合A、集合B继续取某个值当临界点，重复上面的操作，直到分区后的集合数量只含一个元素，此时这N个数据就排好序了。 关键的是分区操作，假如这n个数据组成的数组S的角标是从0到n-1，先取最后一个值separator = S[n-1]，我们的目的是用游标i把集合S分为两部分，左侧的是已处理区间（游标i），右侧的是未处理区间（游标j）。首先i=0（后面会慢慢变大）, j从0到n-1,如果S[j]<separator,表明未处理区间的数字比已处理区间的数字小，这怎么可以呢？我们的宗旨就是让separator左边区间都比separator小！于是这时就要让S[j]和S[i]这两个值互换位置，也就是未处理的某数据S[j]到了已处理的部分,因为已处理的部分多了一个数据，所以要让i=i+1，然后依次继续比较S[j+1]和separator、S[j+2]和separator…S[n-1]和separator，当游标j这一轮循环结束的时候，此时j=n-1，但是S[i]作为未处理部分的第一个元素，肯定比separator大，所以这时交换一下S[i]和S[n-1]，如此重复即可获取分区点
到此，快速排序的原理你应该也掌握了。现在，我再来看另外一个问题：快排和归并用的都是分治思想，递推公式和递归代码也非常相似，那它们的区别在哪里呢？
可以发现，归并排序的处理过程是由下到上的，先处理子问题，然后再合并。而快排正好相反，它的处理过程是由上到下的，先分区，然后再处理子问题。归并排序虽然是稳定的、时间复杂度为 O(nlogn) 的排序算法，但是它是非原地排序算法。我们前面讲过，归并之所以是非原地排序算法，主要原因是合并函数无法在原地执行。快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。
# 快速排序的性能分析
现在，我们来分析一下快速排序的性能。我在讲解快排的实现原理的时候，已经分析了稳定性和空间复杂度。快排是一种原地、不稳定的排序算法。现在，我们集中精力来看快排的时间复杂度。
快排也是用递归来实现的。对于递归代码的时间复杂度，我前面总结的公式，这里也还是适用的。如果每次分区操作，都能正好把数组分成大小接近相等的两个小区间，那快排的时间复杂度递推求解公式跟归并是相同的。所以，快排的时间复杂度也是 O(nlogn)。
T(1) = C； n=1 时，只需要常量级的执行时间，所以表示为 C。
T(n) = 2*T(n/2) + n； n>1
但是，公式成立的前提是每次分区操作，我们选择的 pivot 都很合适，正好能将大区间对等地一分为二。但实际上这种情况是很难实现的。
我举一个比较极端的例子。如果数组中的数据原来已经是有序的了，比如 1，3，5，6，8。如果我们每次选择最后一个元素作为 pivot，那每次分区得到的两个区间都是不均等的。我们需要进行大约 n 次分区操作，才能完成快排的整个过程。每次分区我们平均要扫描大约 n/2 个元素，这种情况下，快排的时间复杂度就从 O(nlogn) 退化成了 O(n2)。
我们刚刚讲了两个极端情况下的时间复杂度，一个是分区极其均衡，一个是分区极其不均衡。它们分别对应快排的最好情况时间复杂度和最坏情况时间复杂度。那快排的平均情况时间复杂度是多少呢？
我们假设每次分区操作都将区间分成大小为 9:1 的两个小区间。我们继续套用递归时间复杂度的递推公式，就会变成这样：
T(1) = C； n=1 时，只需要常量级的执行时间，所以表示为 C。
T(n) = T(n/10) + T(9*n/10) + n； n>1
这个公式的递推求解的过程非常复杂，虽然可以求解，但我不推荐用这种方法。实际上，递归的时间复杂度的求解方法除了
递推公式之外，还有递归树，在树那一节我再讲，这里暂时不说。我这里直接给你结论：T(n) 在大部分情况下的时间复杂度都可以做到 O(nlogn)，只有在极端情况下，才会退化到 O(n2)。而且，我们也有很多方法将这个概率降到很低，如何来做？我们后面章节再讲。
# 线性排序
# 桶排序（Bucket sort）
桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。
比如说我们有 10GB 的订单数据，我们希望按订单金额（假设金额都是正整数）进行排序，但是我们的内存有限，只有几百 MB，没办法一次性把 10GB 的数据都加载到内存中。这个时候该怎么办呢？
# 计数排序（Counting sort）
Panda总结：n个原始数据组成的数组A，数据大小范围在0-k之间，先扫描一遍A，获得最大值max，然后统计大小为x的数据有多少个，存到数组C里面，比如C[x]=3 等，然后依次计算数组C的前n项和，赋值给C[n-1]，然后新建数组R，循环这n个原始数据，让R[C[A[i]]]= A[i], 同时C[A[i]] 减一，次循环结束后，R就是一个排序好的数组了，在循环n次，使A[i]=R[i]，A也会是排序好的数组了
如果你所在的省有 50 万考生，如何通过成绩快速排序得出名次呢？
考生的满分是 900 分，最小是 0 分，这个数据的范围很小，所以我们可以分成 901 个桶，对应分数从 0 分到 900 分。根据考生的成绩，我们将这 50 万考生划分到这 901 个桶里。桶内的数据都是分数相同的考生，所以并不需要再进行排序。我们只需要依次扫描每个桶，将桶内的考生依次输出到一个数组中，就实现了 50 万考生的排序。因为只涉及扫描遍历操作，所以时间复杂度是 O(n)。
计数排序的算法思想就是这么简单，跟桶排序非常类似，只是桶的大小粒度不一样。不过，为什么这个排序算法叫“计数”排序呢？“计数”的含义来自哪里呢？
想弄明白这个问题，我们就要来看计数排序算法的实现方法。我还拿考生那个例子来解释。为了方便说明，我对数据规模做了简化。假设只有 8 个考生，分数在 0 到 5 分之间。这 8 个考生的成绩我们放在一个数组 A[8] 中，它们分别是：2，5，3，0，2，3，0，3。
考生的成绩从 0 到 5 分，我们使用大小为 6 的数组 C[6] 表示桶，其中下标对应分数。不过，C[6] 内存储的并不是考生，而是对应的考生个数。像我刚刚举的那个例子，我们只需要遍历一遍考生分数，就可以得到 C[6] 的值。
从图中可以看出，分数为 3 分的考生有 3 个，小于 3 分的考生有 4 个，所以，成绩为 3 分的考生在排序之后的有序数组 R[8] 中，会保存下标 4，5，6 的位置。
那我们如何快速计算出，每个分数的考生在有序数组中对应的存储位置呢？这个处理方法非常巧妙，很不容易想到。
思路是这样的：我们对 C[6] 数组顺序求和，C[6] 存储的数据就变成了下面这样子。C[k] 里存储小于等于分数 k 的考生个数。
有了前面的数据准备之后，现在我就要讲计数排序中最复杂、最难理解的一部分了，请集中精力跟着我的思路！
我们从后到前依次扫描数组 A。比如，当扫描到 3 时，我们可以从数组 C 中取出下标为 3 的值 7，也就是说，到目前为止，包括自己在内，分数小于等于 3 的考生有 7 个，也就是说 3 是数组 R 中的第 7 个元素（也就是数组 R 中下标为 6 的位置）。当 3 放入到数组 R 中后，小于等于 3 的元素就只剩下了 6 个了，所以相应的 C[3] 要减 1，变成 6。
以此类推，当我们扫描到第 2 个分数为 3 的考生的时候，就会把它放入数组 R 中的第 6 个元素的位置（也就是下标为 5 的位置）。当我们扫描完整个数组 A 后，数组 R 内的数据就是按照分数从小到大有序排列的了。
上面的过程有点复杂，我写成了代码，你可以对照着看下。
// 计数排序，a 是数组，n 是数组大小。假设数组中存储的都是非负整数。
public void countingSort(int[] a, int n) {
if (n <= 1) return;
// 查找数组中数据的范围
int max = a[0];
for (int i = 1; i < n; ++i) {
if (max < a[i]) {
max = a[i];
}
}
int[] c = new int[max + 1]; // 申请一个计数数组 c，下标大小 [0,max]
for (int i = 0; i <= max; ++i) {
c[i] = 0;
}
// 计算每个元素的个数，放入 c 中
for (int i = 0; i < n; ++i) {
c[a[i]]++;
}
// 依次累加
for (int i = 1; i <= max; ++i) {
c[i] = c[i-1] + c[i];
}
// 临时数组 r，存储排序之后的结果
int[] r = new int[n];
// 计算排序的关键步骤，有点难理解
for (int i = n - 1; i >= 0; --i) {
int index = c[a[i]]-1;
r[index] = a[i];
c[a[i]]--;
}
// 将结果拷贝给 a 数组
for (int i = 0; i < n; ++i) {
a[i] = r[i];
}
}
这种利用另外一个数组来计数的实现方式是不是很巧妙呢？这也是为什么这种排序算法叫计数排序的原因。不过，你千万不要死记硬背上面的排序过程，重要的是理解和会用。
我总结一下，计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。
比如，还是拿考生这个例子。如果考生成绩精确到小数后一位，我们就需要将所有的分数都先乘以 10，转化成整数，然后再放到 9010 个桶内。再比如，如果要排序的数据中有负数，数据的范围是 [-1000, 1000]，那我们就需要先对每个数据都加 1000，转化成非负整数。
# 基数排序（Radix sort）
有时候要排序的数据并不都是等长的，比如我们排序牛津字典中的 20 万个英文单词，最短的只有 1 个字母，最长的我特意去查了下，有 45 个字母，中文翻译是尘肺病。对于这种不等长的数据，基数排序还适用吗？
实际上，我们可以把所有的单词补齐到相同长度，位数不够的可以在后面补“0”，因为根据ASCII 值 (opens new window)，所有字母都大于“0”，所以补“0”不会影响到原有的大小顺序。这样就可以继续用基数排序了。
我来总结一下，基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到 O(n) 了。
假设我们现在需要对 D，a，F，B，c，A，z 这个字符串进行排序，要求将其中所有小写字母都排在大写字母的前面，但小写字母内部和大写字母内部不要求有序。比如经过排序之后为 a，c，z，D，F，B，A，这个如何来实现呢？如果字符串中存储的不仅有大小写字母，还有数字。要将小写字母的放到前面，大写字母放在最后，数字放在中间，不用排序算法，又该怎么解决呢？
用两个指针a、b: a指针从头开始往后遍历，遇到大写字母就停下，b从后往前遍历，遇到小写字母就停下，交换a、b指针对应的元素;重复如上过程，直到a 、b指针相交。 对于小写字母放前面，数字放中间，大写字母放后面，可以先将数据分为小写字母和非小写字母两大类，进行如上交换后再在非小写字母区间内分为数字和大写字母做同样处理
# 快速排序优化
- 三数取中法
我们从区间的首、尾、中间，分别取出一个数，然后对比大小，取这 3 个数的中间值作为分区点。这样每间隔某个固定的长度，取数据出来比较，将中间值作为分区点的分区算法，肯定要比单纯取某一个数据更好。但是，如果要排序的数组比较大，那“三数取中”可能就不够了，可能要“五数取中”或者“十数取中”。
- 随机法
每次从要排序的区间中，随机选择一个元素作为分区点。
为了避免快速排序里，递归过深而堆栈过小，导致堆栈溢出，我们有两种解决办法：第一种是限制递归深度。一旦递归过深，超过了我们事先设定的阈值，就停止递归。第二种是通过在堆上模拟实现一个函数调用栈，手动模拟递归压栈、出栈的过程，这样就没有了系统栈大小的限制。