波波老师，请教您一个关于快排的疑问。

来源：2-3 实现双路快速排序法

LanceMai

2020-08-31 16:20:47

我发现加 = 和不加 = 的区别挺大的。如果是在一个容量大，但是数据范围小的数组中排序，加了等号以后速度会慢很多。如下图所示，这是我测试的实验结果。"QuickSortD" 代表双路快排，"QuickSort3" 是第一章实现的快排代码，主要观察 "QuickSortD" 所耗的时间。数据量我设置的是 200 0000，bound 我设定的是 1000。按这样的设定，在数组中必定有很多重复的数据，但为什么仅添加一个 = 效果就会差这么多？

写回答

1回答

liuyubobobo

2020-09-01

这就是在这一小节我的这个算法实现的关键啊！

上一小节的动画演示，4 分钟的位置，请再听一遍：https://class.imooc.com/lesson/1582#mid=37045

10 分钟的位置我针对包含有相同元素的数组进行了模拟，请再看一遍。并且思考一下，如果没有等于，这个模拟会是什么样子？

===================

在一个有 100 个 1 的数组中，如果 while 中有等号，循环将走到头才会终止，最终划分出的标定点还是在极端的位置；

但如果没有等号，在相等的时候就终止，才能保证最终的标定点在中间。

使用一个小数据量，再在代码中实际测试一下试试看？比如有 8 个 1 的数组，单步跟踪，看看有等号，最终的结果是谁？为什么？没等号，最终的结果是谁？为什么？

加油！：）

hanceMai

h 我懂老师的意思了，在等于的时候，i 或者 j 就会停下来，进行交换，这也相当于两边都包含相等的元素。循环不变量中 = 的含义来的委婉一些罢了。如果直接在 while 中使用 = ，看起来是符合循环不变量的定义，但是在元素都相等的极端情况下，会出现返回的一端有元素，另一端没有元素的极端情况，从而造成递归深度为 O(n) 的情况。

h020-09-01

共1条回复

算法与数据结构

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

2610 学习 · 1087 问题

查看课程

相似问题

快速排序中Knuth optimized quicksort

回答 1

关于双路快排的疑问

回答 2

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

回答 1

三路快速排序算法

回答 1

所谓的算法都是指排序查找吗？

回答 1

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