擅长:python、mysql、java
<p>我认为,第9页的代码在第8页的图表中解释得很好:首先进行分区,然后将与轴相等的元素交换到向量的边上,因此结果是:</p>
<pre><code>[equals-left] [lesses] [greaters] [equals-right]
</code></pre>
<p>然后将相等的元素交换回中心:</p>
^{2}$
<p>然后递归排序<code>[lesses]</code>和{<cd2>}</p>
<p>Sedgwick的假设是数据集中有许多重复的元素。在这种情况下,轴心被重复是很常见的,如果是这样的话,你可以通过不在任何一个快速排序递归中包含轴心的任何重复来获得一些好处,这样两个分区之和的大小将小于矢量的大小乘以轴心的重复次数(即使它只是这减少了需要递归的元素的数量,这使得递归更快。在</p>
<p>这样做的成本是每个元素一到两个额外的比较,尽管两个元素都只是用不同的成功条件重复前面的比较。在比较比较比较复杂的情况下,您可能需要使用显式的三向比较函数,以便能够保存上一次<;比较的结果(在Sedgwick代码中的while循环中)。如果这个支点没有重复,那就是额外的成本:那些额外的比较。如果pivot是重复的,那么每个重复的pivot元素有一个或两个额外的交换和两个或一个额外的比较(因此,如果swap和compare花费相同的时间,则需要三个额外的操作),再加上每个其他元素的两个额外比较。在</p>
<p>这值得吗?我很怀疑,但如果塞奇威克说是的话,那你应该听他的,而不是我。在</p>