昨天晚上睡觉前兴起准备十分钟写出快排，结果纠结了两个小时愣是没有搞出来，很郁闷地睡觉去。今天地铁上跟LG又重新缕了一遍思路，到了公司十分钟搞定。

三个关键点：

1. 基准点的选取对过程的影响。如果选取最左边的点作为基准点，那么需要先从右边开始比较；相反，如果选取最右边的点为基准点，则需要从左边开始比较。这样做可以避免当整个数列本身就是已排序状态的时候基准点被换到错误的位置上去。

2. 主要逻辑循环部分的出口是i==j。在比较过程中，一定要控制i<j，否则很容易OutOfIndex...

3. 主循环的作用是要找到基准点的正确位置。因此，当i=j之后，一点要将基准点换到这个位置上；整个数列也因此被分成两个小的数列。进而递归，分而治之。

快速排序

将算法除递归之外的部分抽取出来，可以得到一个partition方法来返回基准点的正确位置。借用同样的思路（PARTITION+递归），可以解决选择问题，即从数列中找到第K小或者第K大的问题。

选择第K小问题

注意点是：kthMin方法中的下标计算。