博主秋招提前批已拿百度、字节跳动、拼多多、顺丰等公司的offer，可加微信：pcwl_Java  一起交流秋招面试经验。

目  录：

方法1：暴力解法

方法2：快排实现【笔试版+面试版】

方法3：BFPRT 算法实现【面试优化版】

---

问题：求一个数组中的第 k 小 / 大的数。

说明：这道题求解不难，主要的目的是为了引出 快排算法的应用（partiotion）和 BFPRT 算法

 其实我们很容易想到先将这个数组排好序，再直接取出数组中下标为 k - 1 的数即可。

---

快速排序将比关键字大的元素从前面移动到后面，比关键字小的元素从后面直接移动到前面，从而减少了总的比较次数和移动次数，同时采用”分而治之“的思想，把大的拆分为小的，小的再拆分为更小的，其原理如下：通过一趟排序将待排序的数组分成两个部分，其中一部分记录的是比关键字更小的，另一部分是比关键字更大的，然后再分别对着两部分继续进行排序，直到整个序列有序；

步骤：代码也很容易理解，其实就是一个“填坑”的过程，

1、第一个“坑”挖在每次排序的第一个位置 arr[low]，从序列后面往前找第一个比 pivot 小的数来把这个“坑”填上，这时候的“坑”就变成了当前的 arr[high]；

2、然后再从序列前面往后用第一个比 pivot 大的数把刚才的“坑”填上；

    以上就是本篇文章【【搞定算法】BFPRT 算法、快排解决第 k 大数问题】的全部内容了，欢迎阅览 ！ 文章地址：http://w.yusign.com/news/4281.html 
     资讯      企业新闻      行情      企业黄页      同类资讯      首页      网站地图      返回首页 述古往 http://w.yusign.com/mobile/ , 查看更多