复习快排的时候想到的，这里记录一下。
先看一下比较容易理解的快排算法（摘自维基）：
function quicksort(q)
{
var list less, pivotList, greater
if length(q) ≤ 1
return q
else
{
select a pivot value pivot from q
for each x in q except the pivot element
{
if x < pivot then add x to less
if x ≥ pivot then add x to greater
}
add pivot to pivotList
return concatenate(quicksort(less), pivotList, quicksort(greater))
}
}
大家都说快排是不稳定的，想到个算法，发现和知乎这个问题一致（即选取pivot时总是选取第一个）：https://www.zhihu.com/question/45929062
不难发现，对于上面这个简单的快排算法来说，这种优化使得其是稳定的。
高票的回答应该是指复杂版的in-place算法。
我们可以模拟一下排序的过程，第一轮各元素与pivot比较时，总共需要n次比较操作。
第二轮比较时，左边的元素需要与左边的pivot比较，右边的元素需要与右边的pivot比较，总共也需要n次比较操作。
这样，做多少轮比较，时间复杂度就是多少乘以n。因快排将队列分成了左边和右边，也即是说可以将这个过程想像成一颗二叉树。在最好的情况下，就是树的深度最浅的情况，需要log n轮。在最坏的情况下，树退化成列表，需要n轮。所以最好和最坏的复杂度分别为n*log n和n^2。在平均情况下，这还是一颗二叉树，深度差不多也是log n（乘以一个系数）。
同样与递归深度相关，原地+尾递归版的log n。
因为需要线程独享，所以底层实现是把线程独享的数据放在threadLocals（ThreadLocalMap类）成员变量里。
在ThreadLocal某一实例执行get时，内部通过Thread类静态方法currentThread获取当前线程，并返回独享的threadLocals。
然后ThreadLocal以自己为key，在ThreadLocalMap里找到value。
这样，为了在threadLocals里存放多个ThreadLocal实例，threadLocals设计为ThreadLocalMap，ThreadLocal为key，值为相应set的value。
ThreadLocalMap实现上是一个hash map，但并不继承HashMap。解决hash冲突的方法是线性探测线性探测再散列。
ThreadLocalMap自定义了一个Entry，key为弱引用（关于弱引用： Java 如何有效地避免OOM：善于利用软引用和弱引用 ）。
考虑到普遍是用线程池来进行线程的操作，而线程池中的Thread不一定会被回收，为了使弱引用（Entry）对应的对象能够被回收，一般需要在ThreadLocal使用完后进行remove()将相应的强引用置为null。
ThreadLocal同样实现了get()、set()过程中的惰性清除。
VS 二叉平衡树
VS B树
VS HASH 在一下方面效率更高
跳表与B+树很像，在原始链表的基础上一级一级的增加索引实现。增删查的复杂度都为log n。
与红黑树相比，优点在于可以高效支持区间查找。
与B+树相比，优点在于算法简单。
用法：