分治思想-选pivot问题
前言选择的pivot会影响比较次数。为了进一步理解如何选pivot，我们从找出数组中第k小的数问题入手来理解。例子：寻找第k小的元素问题叙述给定一个乱序数组A，试求该数组中第k小的元素？最直接的解决办法就是数组排序返回index为k-1的元素，排序选用快排或归并（若不考虑内存使用），时间复杂度是O(nlogn)。思考一下，实际上这个问题没有必要将数组完全排序再找第k个元素。解决思路参考快排的策略，我们可以有思路，将小于pivot的放到左边，大于pivot的放到右边。试想，如果有一个数左边的数
