快排优化：举一反三，轻松面对快排面试题

问题一：在一堆无序的数字中查找第 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讲》，强烈推荐该课程！