博主秋招提前批已拿百度、字节跳动、拼多多、顺丰等公司的offer，可加微信：pcwl_Java 一起交流秋招面试经验。
目 录：
方法1：暴力解法
方法2：快排实现【笔试版+面试版】
方法3：BFPRT 算法实现【面试优化版】
问题：求一个数组中的第 k 小 / 大的数。
说明：这道题求解不难，主要的目的是为了引出 快排算法的应用（partiotion）和 BFPRT 算法
其实我们很容易想到先将这个数组排好序，再直接取出数组中下标为 k - 1 的数即可。
快速排序将比关键字大的元素从前面移动到后面，比关键字小的元素从后面直接移动到前面，从而减少了总的比较次数和移动次数，同时采用”分而治之“的思想，把大的拆分为小的，小的再拆分为更小的，其原理如下：通过一趟排序将待排序的数组分成两个部分，其中一部分记录的是比关键字更小的，另一部分是比关键字更大的，然后再分别对着两部分继续进行排序，直到整个序列有序；
步骤：代码也很容易理解，其实就是一个“填坑”的过程，
1、第一个“坑”挖在每次排序的第一个位置 arr[low]，从序列后面往前找第一个比 pivot 小的数来把这个“坑”填上，这时候的“坑”就变成了当前的 arr[high]；
2、然后再从序列前面往后用第一个比 pivot 大的数把刚才的“坑”填上；