2
条回答
写回答
写回答
-
chiconysun说的很好，做一点小小的补充：
在数据量较大时，递归调用本身的消耗对算法的时间效率也会产生一定影响，采用非递归实现，或者在待排序区间小于某值（有实验数据表明15左右较合适）时，采用其它非递归的排序方法代替快速排序，可以达到更高的时间效率。
相对于关键值的选取，这一优化带来的提升有限（亲测结果，提升10%左右，选择了插入排序做替代）。2019-07-17 22:49:45赞同 展开评论 打赏 -
杀人者，打虎武松也。一般快速排序算法都是以最左元素作为划分的基准值，这样当数据元素本身已经完全有序（不管正序或者逆序）时，每一趟划分只能将一个元素分割出来，其效率很低：时间复杂度O(n^2)，空间复杂度为O(n)
所以改进方法就是找寻合适的基准值，保证不至于在关键字有序或者接近有序时发生这个情况，一般可以使用三者取中（就是待划分序列的头元素、尾元素、中间元素三者的中间值）、或者随机选择等方法，这样即使关键字完全有序，也可以保证时间复杂度O(nlogn)，空间复杂度O(logn)2019-07-17 22:49:44赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
相关问答
问答排行榜
最热
最新
推荐问答
