对一个完全有序的数组，用插入排序进行优化，反而慢的不可思议

Question

Answer 1

liuyubobobo 2019-07-29 18:24:54

你的快排没有加入随机化，对于完全有序的数组，没有随机化的快排就会退化成为O(n^2)级别的算法啊。

再仔细看一下这一小节，这就是我们要为快排添加随机化的原因：）

继续加油！：）

• 提问者 无心铁憨憨 #1

  我有加入随机化啊

• liuyubobobo 回复 提问者 无心铁憨憨 #2

  哦，刚看到。那大概率的是你的算法实现有问题。如果你是在加入插入排序后产生的效率问题，大概率的问题在你的插入排序的部分。比如，你的插入排序是不是只对l到r的元素进行的排序？还是对整个数组进行排序？可以尝试运行课程的官方代码，看是否有同样的问题？如果没有问题，请仔细调试比对你，看自己的代码哪里有问题。课程官方代码传送门：https://github.com/liuyubobobo/Play-with-Algorithms 加油！：）

• 提问者 无心铁憨憨 回复 liuyubobobo #3

  好的，等会回去再仔细看看

点开查看后面4条评论