Open wangjunstf opened 2 years ago
https://wangjunstf.github.io/2021/10/24/kuai-su-pai-xu-de-bian-chong-kuai-su-xuan-ze-suan-fa/
快速排序的变种——快速选择算法给出一个数组,例如[1,4,2,6,8,3],现在要求出第 k 大的数字,即将数组从大到小排列,选择第k个数。用什么算法更快找到这个数? 最容易想到的就是先将数组排序,就可以很容易找到第 k 大的数字。就算用快速排序,时间复杂度为 O(nlgn)。有没有更快的算法?
https://wangjunstf.github.io/2021/10/24/kuai-su-pai-xu-de-bian-chong-kuai-su-xuan-ze-suan-fa/
快速排序的变种——快速选择算法给出一个数组,例如[1,4,2,6,8,3],现在要求出第 k 大的数字,即将数组从大到小排列,选择第k个数。用什么算法更快找到这个数? 最容易想到的就是先将数组排序,就可以很容易找到第 k 大的数字。就算用快速排序,时间复杂度为 O(nlgn)。有没有更快的算法?