快速选择算法

目录

如何在 n 个没有排序的元素中找到第 k(小/大)的元素,1<=k<=n。这里介绍一种用于解决这个问题的算法:快速选择算法

时间复杂度

最坏 平均
O(n^2) O(n)

算法过程

quickselect_algorithm_1.png

  如上图我们有一个没有排序的数组 A 有 L 个元素,我们要找到第 k 小的元素,算法步骤如下。
定义 len(n) 是 n 元素到最左边元素的长度
1.假如我们选的元素是 n,然后把小于等于 n 的元素放在 n 的左边,大于 n 的元素放在 n 的右边
2.如果 len(n) = k,则我们刚好找到第 k 大的元素就是 n
3.如果 len(n) < k,则我需要在 n 到最右边的元素中找第 k - len(n)  个元素

4.假如我们选的元素是 n1,然后把小于等于 n1 的元素放在 n1 的左边,大于 n1 的元素放在 n1 的右边
5.如果 len(n1) = k,则我们刚好找到第 k 大的元素就是 n1
6.如果 len(n1) > k,则我需要在 n1 到最左边的元素中找第 k 个元素
7.重复这个过程直到找第 k 大的元素

# 找第 k 大的算法稍微变化一下就得到了

目录