本周算法：快速排序—三路快排 vs 双基准

逃离我推掉我的手 2022-09-20 09:18 202阅读 0赞

http://www.importnew.com/8445.html

原文链接： [ dzone][dzone] 翻译： [ImportNew.com ][ImportNew.com] \- [风恋星][Link 1]  
译文链接： [http://www.importnew.com/8445.html][http_www.importnew.com_8445.html]  
\[ **转载请保留原文出处、译者和译文链接。**\]  
  
**本文由 [ImportNew][ImportNew.com] \- [ 风恋星][Link 1] 翻译自 [ dzone][dzone]。如需转载本文，请先参见文章末尾处的转载要求。**

*ImportNew注：如果你也对Java技术翻译分享感兴趣，欢迎加入我们的 [ Java开发][Java] 小组。参与方式请查看[小组][Java]简介。*

快速排序被公认为是本世纪最重要的算法之一，这已经不是什么新闻了。对很多语言来说是实际系统排序，包括在Java中的`Arrays.sort`。

**那么快速排序有什么新进展呢？**

好吧，就像我刚才提到的那样（Java 7发布两年后）快速排序实现的`Arrays.sort`被**双基准（dual-pivot）**排序的一种变体取代了。[这篇文章][Link 2]不仅展示了为什么这个变化如此优秀，而且让我们看到Jon Bentley和Joshua Bloch的谦逊。

**我当时做了什么？**

与所有人一样，我想实现这个算法并且对一千万个数值排序（随机数据和重复数据）。奇怪的是，我得到了下面的结果：

**随机数据：**

*  基本排序：1222ms。
 *  三路（Three-way）快速排序：1295ms（我是认真的！）。
 *  双基准快速排序：1066ms。

**重复数据：**

*  基本排序：378ms。
 *  三路快速排序：15ms。
 *  双基准快速排序：6ms。

**愚蠢的问题1**

我担心自己在实现三路快速排序的时候遗漏了什么。在多次执行随机输入一千万个数值后，可以看到单点排序始终运行更良好。尽管在执行一千万个数值的时候差距小于100ms。

我现在明白了，用三路快速排序作为默认排序工具的目的。因为在重复数值时，它的时间复杂度没有0(n2)。当我在输入重复值数据时，结果非常明显。但是真的为了处理重复数据的缘故，三路快速排序会受到性能损失吗？或者是我实现方式有问题？

**愚蠢的问题2**

我的双基准快速排序在实现重复数据的时候并没有处理好，它执行时耗费了0(n2)的时间复杂度。有什么好的办法可以避免吗？实现数组排序时我发现，在实际排序前升序序列和重复就已经能得到很好地消除。所以，作为一种应急的办法，如果定位的数字与比较的数字相等，则增长*lowerIndex* 去比较下一位数直到与*pivot2*不相等为止。这种实现会没有问题吗？

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      1 
    </div> 
    <div>
      2 
    </div> 
    <div>
      3 
    </div> 
    <div>
      4 
    </div> 
    <div>
      5 
    </div> 
    <div>
      6 
    </div> </td> 
   <td> 
    <div> 
     <div> 
      <code>else</code> 
      <code> if</code> 
      <code>(pivot1==pivot2){ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>while</code> 
      <code>(pivot1==pivot2 &amp;&amp; lowIndex&lt;highIndex){ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>lowIndex++; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>pivot1=input[lowIndex]; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;</code> 
      <code>}</code> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

**这就是所有内容吗？我究竟做了哪些？**

我一直觉得算法跟踪很有趣，但是双基准快速排序中出现的变量个数让我眼花缭乱。所以，接下来我在（三种）实现中都加入了调试信息，这样就可以看出实际运行中不同。

这些可跟踪的类只负责追踪数组下方的指针。希望你能发现这些类是很有用的。

例如一个双基准迭代器：

[![QuickSortTracing.png][]][QuickSortTracing.png 1]

**你可以从哪里下载代码？**

整个项目（连同一些蹩脚的DSA实现）的实现可以在[GitHub][]上找到。快速排序类就可以在[这里][Link 3]找到。

这是我的实现单基准（Hoare），三路快排（Sedgewick）和新双基准（Yaroslavskiy）。

**单基准：**

[![Optimized-SinglePivot.png.jpg][]][Optimized-SinglePivot.png.jpg 1]

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      1 
    </div> 
    <div>
      2 
    </div> 
    <div>
      3 
    </div> 
    <div>
      4 
    </div> 
    <div>
      5 
    </div> 
    <div>
      6 
    </div> 
    <div>
      7 
    </div> 
    <div>
      8 
    </div> 
    <div>
      9 
    </div> 
    <div>
      10 
    </div> 
    <div>
      11 
    </div> 
    <div>
      12 
    </div> 
    <div>
      13 
    </div> 
    <div>
      14 
    </div> 
    <div>
      15 
    </div> 
    <div>
      16 
    </div> 
    <div>
      17 
    </div> 
    <div>
      18 
    </div> 
    <div>
      19 
    </div> 
    <div>
      20 
    </div> 
    <div>
      21 
    </div> 
    <div>
      22 
    </div> 
    <div>
      23 
    </div> 
    <div>
      24 
    </div> 
    <div>
      25 
    </div> 
    <div>
      26 
    </div> 
    <div>
      27 
    </div> 
    <div>
      28 
    </div> 
    <div>
      29 
    </div> 
    <div>
      30 
    </div> 
    <div>
      31 
    </div> 
    <div>
      32 
    </div> 
    <div>
      33 
    </div> 
    <div>
      34 
    </div> 
    <div>
      35 
    </div> 
    <div>
      36 
    </div> 
    <div>
      37 
    </div> 
    <div>
      38 
    </div> 
    <div>
      39 
    </div> 
    <div>
      40 
    </div> 
    <div>
      41 
    </div> 
    <div>
      42 
    </div> 
    <div>
      43 
    </div> 
    <div>
      44 
    </div> 
    <div>
      45 
    </div> 
    <div>
      46 
    </div> 
    <div>
      47 
    </div> 
    <div>
      48 
    </div> 
    <div>
      49 
    </div> 
    <div>
      50 
    </div> 
    <div>
      51 
    </div> 
    <div>
      52 
    </div> 
    <div>
      53 
    </div> 
    <div>
      54 
    </div> </td> 
   <td> 
    <div> 
     <div> 
      <code>package</code> 
      <code> basics.sorting.quick; </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>import</code> 
      <code> static</code> 
      <code>basics.sorting.utils.SortUtils.exchange; </code> 
     </div> 
     <div> 
      <code>import</code> 
      <code> static</code> 
      <code>basics.sorting.utils.SortUtils.less; </code> 
     </div> 
     <div> 
      <code>import</code> 
      <code> basics.shuffle.KnuthShuffle; </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>public</code> 
      <code> class</code> 
      <code>QuickSortBasic { </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;</code> 
      <code>public</code> 
      <code>void</code> 
      <code>sort (</code> 
      <code>int</code> 
      <code>[] input){ </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>//KnuthShuffle.shuffle(input); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>sort (input, </code> 
      <code>0</code> 
      <code>, input.length-</code> 
      <code>1</code> 
      <code>); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;</code> 
      <code>private</code> 
      <code>void</code> 
      <code>sort(</code> 
      <code>int</code> 
      <code>[] input, </code> 
      <code>int</code> 
      <code>lowIndex, </code> 
      <code>int</code> 
      <code>highIndex) { </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>if</code> 
      <code>(highIndex&lt;=lowIndex){ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code> 
      <code>; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>int</code> 
      <code>partIndex=partition (input, lowIndex, highIndex); </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>sort (input, lowIndex, partIndex-</code> 
      <code>1</code> 
      <code>); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>sort (input, partIndex+</code> 
      <code>1</code> 
      <code>, highIndex); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;</code> 
      <code>private</code> 
      <code>int</code> 
      <code>partition(</code> 
      <code>int</code> 
      <code>[] input, </code> 
      <code>int</code> 
      <code>lowIndex, </code> 
      <code>int</code> 
      <code>highIndex) { </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>int</code> 
      <code>i=lowIndex; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>int</code> 
      <code>pivotIndex=lowIndex; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>int</code> 
      <code>j=highIndex+</code> 
      <code>1</code> 
      <code>; </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>while</code> 
      <code>(</code> 
      <code>true</code> 
      <code>){ </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>while</code> 
      <code>(less(input[++i], input[pivotIndex])){ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>if</code> 
      <code>(i==highIndex) </code> 
      <code>break</code> 
      <code>; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>while</code> 
      <code>(less (input[pivotIndex], input[--j])){ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>if</code> 
      <code>(j==lowIndex) </code> 
      <code>break</code> 
      <code>; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>if</code> 
      <code>(i&gt;=j) </code> 
      <code>break</code> 
      <code>; </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>exchange(input, i, j); </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>exchange(input, pivotIndex, j); </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code> 
      <code>j; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>}</code> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

**三基准**

[![Optimized-3Way.png.jpg][]][Optimized-3Way.png.jpg 1]

**双基准**

[![Optimized-DualPivot.png.jpg][]][Optimized-DualPivot.png.jpg 1]

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      1 
    </div> 
    <div>
      2 
    </div> 
    <div>
      3 
    </div> 
    <div>
      4 
    </div> 
    <div>
      5 
    </div> 
    <div>
      6 
    </div> 
    <div>
      7 
    </div> 
    <div>
      8 
    </div> 
    <div>
      9 
    </div> 
    <div>
      10 
    </div> 
    <div>
      11 
    </div> 
    <div>
      12 
    </div> 
    <div>
      13 
    </div> 
    <div>
      14 
    </div> 
    <div>
      15 
    </div> 
    <div>
      16 
    </div> 
    <div>
      17 
    </div> 
    <div>
      18 
    </div> 
    <div>
      19 
    </div> 
    <div>
      20 
    </div> 
    <div>
      21 
    </div> 
    <div>
      22 
    </div> 
    <div>
      23 
    </div> 
    <div>
      24 
    </div> 
    <div>
      25 
    </div> 
    <div>
      26 
    </div> 
    <div>
      27 
    </div> 
    <div>
      28 
    </div> 
    <div>
      29 
    </div> 
    <div>
      30 
    </div> 
    <div>
      31 
    </div> 
    <div>
      32 
    </div> 
    <div>
      33 
    </div> 
    <div>
      34 
    </div> 
    <div>
      35 
    </div> 
    <div>
      36 
    </div> 
    <div>
      37 
    </div> 
    <div>
      38 
    </div> 
    <div>
      39 
    </div> 
    <div>
      40 
    </div> 
    <div>
      41 
    </div> 
    <div>
      42 
    </div> 
    <div>
      43 
    </div> 
    <div>
      44 
    </div> 
    <div>
      45 
    </div> 
    <div>
      46 
    </div> 
    <div>
      47 
    </div> 
    <div>
      48 
    </div> 
    <div>
      49 
    </div> 
    <div>
      50 
    </div> 
    <div>
      51 
    </div> 
    <div>
      52 
    </div> 
    <div>
      53 
    </div> 
    <div>
      54 
    </div> 
    <div>
      55 
    </div> 
    <div>
      56 
    </div> 
    <div>
      57 
    </div> 
    <div>
      58 
    </div> 
    <div>
      59 
    </div> 
    <div>
      60 
    </div> 
    <div>
      61 
    </div> </td> 
   <td> 
    <div> 
     <div> 
      <code>package</code> 
      <code> basics.sorting.quick; </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>import</code> 
      <code> static</code> 
      <code>basics.shuffle.KnuthShuffle.shuffle; </code> 
     </div> 
     <div> 
      <code>import</code> 
      <code> static</code> 
      <code>basics.sorting.utils.SortUtils.exchange; </code> 
     </div> 
     <div> 
      <code>import</code> 
      <code> static</code> 
      <code>basics.sorting.utils.SortUtils.less; </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>public</code> 
      <code> class</code> 
      <code>QuickSortDualPivot { </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;</code> 
      <code>public</code> 
      <code>void</code> 
      <code>sort (</code> 
      <code>int</code> 
      <code>[] input){ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>//input=shuffle(input); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>sort (input, </code> 
      <code>0</code> 
      <code>, input.length-</code> 
      <code>1</code> 
      <code>); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;</code> 
      <code>private</code> 
      <code>void</code> 
      <code>sort(</code> 
      <code>int</code> 
      <code>[] input, </code> 
      <code>int</code> 
      <code>lowIndex, </code> 
      <code>int</code> 
      <code>highIndex) { </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>if</code> 
      <code>(highIndex&lt;=lowIndex) </code> 
      <code>return</code> 
      <code>; </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>int</code> 
      <code>pivot1=input[lowIndex]; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>int</code> 
      <code>pivot2=input[highIndex]; </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>if</code> 
      <code>(pivot1&gt;pivot2){ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>exchange(input, lowIndex, highIndex); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>pivot1=input[lowIndex]; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>pivot2=input[highIndex]; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>//sort(input, lowIndex, highIndex); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>else</code> 
      <code>if</code> 
      <code>(pivot1==pivot2){ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>while</code> 
      <code>(pivot1==pivot2 &amp;&amp; lowIndex&lt;highIndex){ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>lowIndex++; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>pivot1=input[lowIndex]; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>int</code> 
      <code>i=lowIndex+</code> 
      <code>1</code> 
      <code>; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>int</code> 
      <code>lt=lowIndex+</code> 
      <code>1</code> 
      <code>; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>int</code> 
      <code>gt=highIndex-</code> 
      <code>1</code> 
      <code>; </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>while</code> 
      <code>(i&lt;=gt){ </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>if</code> 
      <code>(less(input[i], pivot1)){ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>exchange(input, i++, lt++); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>else</code> 
      <code>if</code> 
      <code>(less(pivot2, input[i])){ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>exchange(input, i, gt--); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>else</code> 
      <code>{ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>i++; </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>exchange(input, lowIndex, --lt); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>exchange(input, highIndex, ++gt); </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>sort(input, lowIndex, lt-</code> 
      <code>1</code> 
      <code>); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>sort (input, lt+</code> 
      <code>1</code> 
      <code>, gt-</code> 
      <code>1</code> 
      <code>); </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>sort(input, gt+</code> 
      <code>1</code> 
      <code>, highIndex); </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;</code> 
      <code>} </code> 
     </div> 
     <div> 
      <code>&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>}</code> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

[dzone]: http://java.dzone.com/articles/algorithm-week-quicksort-three
[ImportNew.com]: http://www.importnew.com/
[Link 1]: http://www.importnew.com/author/zhangwangyong
[http_www.importnew.com_8445.html]: http://www.importnew.com/8445.html
[Java]: http://www.jobbole.com/groups/9/
[Link 2]: http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628
[QuickSortTracing.png]: /images/20220828/da79a0b2560c464ca5bff2490c704541.png
[QuickSortTracing.png 1]: http://www.importnew.com/?attachment_id=8448
[GitHub]: https://github.com/arunma/DataStructuresAlgorithms
[Link 3]: https://github.com/arunma/DataStructuresAlgorithms/tree/master/src/basics/sorting/quick
[Optimized-SinglePivot.png.jpg]: /images/20220828/5d159515c08642d3a50f24c9d0a4ce74.png
[Optimized-SinglePivot.png.jpg 1]: http://www.importnew.com/?attachment_id=8449
[Optimized-3Way.png.jpg]: /images/20220828/a57e1357b04a4ca0a80b23a7ef8a235f.png
[Optimized-3Way.png.jpg 1]: http://www.importnew.com/?attachment_id=8450
[Optimized-DualPivot.png.jpg]: /images/20220828/eac5a0b57e34472ca97a7573e173a451.png
[Optimized-DualPivot.png.jpg 1]: http://www.importnew.com/?attachment_id=8451