【编程笔记】快速选择算法

快速选择算法主要用于在一个未排序的数组中寻找第k个最小/最大的数。它的方法类似于快速排序，快速排序和快速选择算法都是Tony Hoare发明的。

快速选择算法思路

只需要每次判断k在左区间还是右区间，一直递归查找k所在的区间。

当只剩下一个数时，数组中就只有一个数，答案是返回数组的值。

平均时间复杂度O(n)，不过最坏情况仍然是O(n^2)

Top K问题

找到未排序的数组中第k个最大的元素。（数组排序后找到第k个最大的元素，而不是第k个不同的元素。）

快速选择算法的过程

这里求的是从小到大排序后的第 k 个数

1.找到分界点x（诸如q[L]，q[(L+R)/2]，q[R]都行）

2.使左边所有数L<=X,右边所有数R>=X（和X相等的数在左右两边都有可能）

3.递归判断k在左右边，当要求的第k个数,k<=j + 1，则递归排序左边，否则递归排序右边。

愉悦，今天的学习很快乐！

夕弦的图片由NovelAI生成，使用的模型以up主红心咖啡_Official的八舞模型为基底，并做了一定的更改训练