快速排序中Knuth optimized quicksort

首页课程实战体系课手记专栏慕课教程

来源：1-9 作业解析：只创建一个 Random 类

v不离不弃v

2020-09-28 23:33:37

波波老师，最近在快排的优化中，我在网上看到了一个叫Knuth optimized quicksort，请问您在您的课中提到了么？是不是这个优化是最好的呢？

写回答

1回答

liuyubobobo

2020-09-29

没有提到，实际上我没有听说过这个优化。你可以给我一个链接我看一下？

不过对于快速排序，课程介绍到这里还远没有结束，下一章还会介绍两个快速排序算法的重要优化，可以继续往后看。

但 anyway，这个课程中介绍的排序算法，很多还有优化余地。但是思想没有本质变化了。很难说某个优化是“最好的优化”，很多时候，的算法细节的优化，通常是对某类数据性能更好，或者是从统计意义的角度去分析的结果。

继续加油！：）

hiuyubobobo

h不离不弃v

h 你的这个网站说的是 knuth shuffle。和快排没关系。knuth shuffle 这个课程最后一章会讲，也可以参考我的公众号文章：https://mp.weixin.qq.com/s?__biz=MzU4NTIxODYwMQ==&mid=2247484310&idx=1&sn=916f92afff6016256648cfb3c7fd83e7&chksm=fd8cacd0cafb25c670587f22524b111d74b4ddd9954070930b6ef6efb1bd8fba13d4250e57d8&token=1282876944&lang=zh_CN#rd 把这个 shuffle 用在快排上，就是一上来对整个数组进行随机乱序，然后再进行快拍的过程，每次就可以选用最左边的元素做标定点了。这本质上和我们每次随机一个标定点是等价的。

h020-09-29

共2条回复

算法与数据结构

波波老师5年集大成之作，算法与数据结构系统学习，考试、面试、竞赛通用

2610 学习 · 1087 问题

查看课程

相似问题

关于第一版和双路快速排序的差异

回答 1

快速排序优化出现内存溢出

回答 1

快速排序主函数的return

回答 1

可以这样来看双路快速排序的算法复杂度吗

回答 1

golang实现快速排序排有序数组是效率低的问题

回答 1

打开慕课网App查看更多内容