如果你学习过算法，那么肯定听说过快速排序的大名，但是对于快速排序中用到的 partition 算法，你了解的够多吗？或许是快速排序太过于光芒四射，使得我们往往会忽视掉同样重要的 partition 算法。

Partition 可不只用在快速排序中，还可以用于 Selection algorithm（在无序数组中寻找第K大的值）中。甚至有可能正是这种通过一趟扫描来进行分类的思想激发 Edsger Dijkstra 想出了 Three-way Partitioning，高效地解决了 Dutch national flag problem 问题。接下来我们一起来探索 partition 算法。

在 深入理解Python中的ThreadLocal变量（上） 中我们看到 ThreadLocal 的引入，使得可以很方便地在多线程环境中使用局部变量。如此美妙的功能到底是怎样实现的？如果你对它的实现原理没有好奇心或一探究竟的冲动，那么接下来的内容估计会让你后悔自己的浅尝辄止了。

简单来说，Python 中 ThreadLocal 就是通过下图中的方法，将全局变量伪装成线程局部变量，相信读完本篇文章你会理解图中内容的。（对这张图不眼熟的话，可以回顾下上篇）。

我们知道多线程环境下，每一个线程均可以使用所属进程的全局变量。如果一个线程对全局变量进行了修改，将会影响到其他所有的线程。为了避免多个线程同时对变量进行修改，引入了线程同步机制，通过互斥锁，条件变量或者读写锁来控制对全局变量的访问。

只用全局变量并不能满足多线程环境的需求，很多时候线程还需要拥有自己的私有数据，这些数据对于其他线程来说不可见。因此线程中也可以使用局部变量，局部变量只有线程自身可以访问，同一个进程下的其他线程不可访问。

有时候使用局部变量不太方便，因此 python 还提供了 ThreadLocal 变量，它本身是一个全局变量，但是每个线程却可以利用它来保存属于自己的私有数据，这些私有数据对其他线程也是不可见的。下图给出了线程中这几种变量的存在情况：