02 | 快排优化：举一反三，轻松面对快排面试题
胡光
你知道快速排序有哪些优化方式吗？快速选择算法和快速排序算法有什么不同？
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
该试读文章来自《常用算法 25 讲》，如需阅读全部文章，
请先通过赠一得一解锁课程
请先通过赠一得一解锁课程
赠一得一
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(30)
- 最新
- 精选
人生苦短老师，针对top K 问题，如果用堆排序，时间复杂度为 nlogK -> n 那这两种算法有什么区别嘛作者回复: topK 问题，根据数据规模不同，我们所采用的解决方法也不同。根据 n 和 k 的范围： n 小 k 小时：快速选择算法 n 大 k 小时：小顶堆 n 大 k 大时：归并排序
245- Geek_c37e49老师，关于对partition的优化有不懂的地方: 对于基准值前后的红绿颜色数量不一定相等吧，可能前面有3个元素要移到后面，有2个元素要移到前面呢
作者回复: 你再想想~~~~前面的位置有限，后面的位置也有限，你把3个移动到后面，就一定会有3个移动到前面。这是脑筋急转弯~~~~^_^
26 
对白我觉得老师对于partition优化部分用两个指针遍历序列代替之前用一个指针遍历序列，并不是减小比较次数，与基准值的比较次数肯定是整个序列的长度，这样才能找到小于和大于基准值的元素，原理应该是通过双指针减少遍历序列需要的时间来提高程序运行效率，希望老师批评指正。作者回复: 首先赞你的思考。d(^_^o)。 下面进入正题，听我说：修改以后的 partition 方法本质上用的是无监督的算法优化思想，其实就是在减少比较次数，而头尾指针遍历次数不变，因为减少了比较次数，所以整体的时间减少了。你再想想。
55
Black Eyed Peterpartition操作优化确实没有明白而且课后参考代码也没有给出来作者回复: 稍等，我看看哈。如果看这个专栏费劲的话，建议你先去看我的编程入门专栏。你可能是一些编程基础的技巧没掌握。
4
JerryZhu单边那个真没看懂， 最后面那个r能起作用吗？ 前面不是递归吗。。作者回复: 你手动模拟一下。另外建议参考我之前写的基础编程课专栏，好好地巩固一下递归的理解。否则沟通成本太高了。
22
枫林火山老师，关于问题1我觉得具体少的比较操作有2点： 老师，首先有个疑问，您的示例代码里是不能出现重复数字的吧，感觉如果有重复，新老方法好像都不对，不知道我说的对不对。 如果排序数组无重复数字，我觉得减少的操作有1点 1. 由于使用的了交换的数必然两两出现的规律，交换前的条件判断少了一半，老方法每个需要交换的数都要判断，新方法每2个需要交换的数判断一次。 2. 老方法由于是填坑法，最后必须保证x或y落在数组index范围内，完成arr[x] = z;的填坑，导致while需要时刻保证x<y。 新方法则不需要保证。因此while内的条件只有一个即可。 脑子不是想的很清楚，请老师指正！作者回复: 是可以出现重复数字的，只是为了让大家更容易理解，没提重复的事情。你可以把等于的数字当成大于基准值，也可以把他当成小于基准值，这是一个思维方面的逻辑变换。不影响的。
21- 杨老师的快速排序原理讲解很清楚 昨天上午自己实现了 不过不是单向的
作者回复: ^_^
21 
刘旺旺讲的清晰明了，点赞👍作者回复: d(^_^o)
李文杰我感觉老师对于partition优化部分用两个指针遍历序列代替之前用一个指针遍历序列，并不是减小比较次数,而是减少了交换次数,从而起到优化作用,而不是减少比较次数26
junjiezou这么多学员对partition的优化没有明白，作者依然不愿意换点更直观的教导方式吗？另外，无端端抛出无监督的思维，但是也没有上下文介绍，怀疑你在虐学员5
收起评论