问题一：在一堆无序的数字中查找第 k 位元素
使用快速排序算法：
- 做了大量的无用操作，这会导致算法效率很低
- 快速排序算法的时间复杂度不稳定，很有可能退化到最坏的时间复杂度 O(n2)
问题二：有没有不需要排序，且效率更高的做法呢？
快速选择算法解决。
快速选择算法是基于快速排序算法的一种拓展算法，它可以在不对数据整体进行排序的前提下，快速找到排名第 k 位的元素，而且时间复杂度还能优化到 O(n)
问题三：在使用快排的情况下，如何才能让它的时间复杂度大概率稳定在 O(nlogn)？
- 优化一：单边递归优化
void quick_sort(int *arr, int l, int r) {while (l < r) {// 进行一轮 partition 操作// 获得基准值的位置int ind = partition(arr, l, r);// 右侧正常调用递归函数quick_sort(arr, ind + 1, r);// 用本层处理左侧的排序r = ind - 1;}
return ;
}- 优化二：基准值选取优化
- 优化三：partition 操作优化
总结：快速选择算法可以用来快速查找一个序列中排名第 k 位的元素；单边递归法可以使快排过程中的递归调用次数减少一半，并且，这种优化方法也可以使用在所有和快速排序类似的程序结构中；三点取中法能帮助我们选出更加合理的基准值，保证快速排序的运行效率；优化 partition 的操作，通过减少程序实现中的比较操作，来提高程序的运行效率。
此文章为3月Day3学习笔记，内容来源于极客时间《常用算法25讲》，强烈推荐该课程！
