PHP版算法--快速排序的实现（第二种方法）

使用第一种方法实现的快速排序相对来说要容易理解一点，第二种方法相对来说不好理解。为此，通过我自己的学习，我画了一张图，以此增加理解记忆。

如果还没有弄明白，那么使用一个最古老的方法，将数组元素值代入到代码中，一遍一遍跑下来，这样巩固了知识又加强了自己的理解。

举个例子：如下文将使用到的数组。

1）$start = 0开始位置

2）$end = 4。4的由来是数组长度减一，因为把基准元素值，单独拿了出来

下面开始代码实现

<span style="box-sizing: border-box;padding-right: 0.1px"><span style="box-sizing: border-box;color: rgb(152, 26, 26)"><?</span><span style="box-sizing: border-box;color: rgb(0, 0, 0)">php</span></span><br></br><span style="box-sizing: border-box;padding-right: 0.1px"><span style="box-sizing: border-box"></span></span><br></br><span style="box-sizing: border-box;padding-right: 0.1px"><span style="box-sizing: border-box;color: rgb(170, 85, 0)">/**</span></span><br></br><span style="box-sizing: border-box;padding-right: 0.1px"> <span style="box-sizing: border-box;color: rgb(170, 85, 0)">* 快速排序</span></span><br></br><span style="box-sizing: border-box;padding-right: 0.1px"> <span style="box-sizing: border-box;color: rgb(170, 85, 0)">* </span></span><br></br><span style="box-sizing: border-box;padding-right: 0.1px"> <span style="box-sizing: border-box;color: rgb(170, 85, 0)">* @param array $arr    待排序的数组</span></span><br></br><span style="box-sizing: border-box;padding-right: 0.1px"> <span style="box-sizing: border-box;color: rgb(170, 85, 0)">* @param int   $start  开始位置</span></span><br></br><span style="box-sizing: border-box;padding-right: 0.1px"> <span style="box-sizing: border-box;color: rgb(170, 85, 0)">* @param int   $end    结束位置</span></span><br></br><span style="box-sizing: border-box;padding-right: 0.1px"> <span style="box-sizing: border-box;color: rgb(170, 85, 0)">* </span></span><br></br><span style="box-sizing: border-box;padding-right: 0.1px"> <span style="box-sizing: border-box;color: rgb(170, 85, 0)">* @return array $arr   排序好的数组</span></span><br></br><span style="box-sizing: border-box;padding-right: 0.1px"> <span style="box-sizing: border-box;color: rgb(170, 85, 0)">**/</span></span><br></br><span style="box-sizing: border-box;padding-right: 0.1px"><span style="box-sizing: border-box;color: rgb(119, 0, 136)">function</span> <span style="box-sizing: border-box;color: rgb(0, 0, 255)">quick_sort_two</span>(<span style="box-sizing: border-box;color: rgb(119, 0, 136)">array</span> <span style="box-sizing: border-box;color: rgb(152, 26, 26)">&</span><span style="box-sizing: border-box;color: rgb(0, 85, 170)">$arr</span>, <span style="box-sizing: border-box;color: rgb(0, 0, 0)">int</span> <span style="box-sizing: border-box;color: rgb(0, 85, 170)">$start</span>, <span style="box-sizing: border-box;color: rgb(0, 0, 0)">int</span> <span style="box-sizing: border-box;color: rgb(0, 85, 170)">$end</span>) {</span><br></br><span style="box-sizing: border-box;padding-right: 0.1px">    <span style="box-sizing: border-box;color: rgb(119, 0, 136)">if</span> (<span style="box-sizing: border-box;color: rgb(0, 85, 170)">$start</span> <span style="box-sizing: border-box;color: rgb(152, 26, 26)">>=</span> <span style="box-sizing: border-box;color: rgb(0, 85, 170)">$end</span>) {</span><br></br><span style="box-sizing: border-box;padding-right: 0.1px">        <span style="box-sizing: border-box;color: rgb(119, 0, 136)">return</span>;</span><br></br><span style="box-sizing: border-box;padding-right: 0.1px">    }</span><br></br><span style="box-sizing: border-box;padding-right: 0.1px"><span style="box-sizing: border-box"></span></span><br></br><span style="box-sizing: border-box;padding-right: 0.1px">    <span style="box-sizing: border-box;color: rgb(0, 85, 170)">$left</span> <span style="box-sizing: border-box;color: rgb(152, 26, 26)">=</span> <span style="box-sizing: border-box;color: rgb(0, 85, 170)">$start</span>;</span><br></br><span style="box-sizing: border-box;padding-right: 0.1px">    <span style="box-sizing: border-box;color: rgb(0, 85, 170)">$right</span> <span style="box-sizing: border-box;color: rgb(152, 26, 26)">=</span> <span style="box-sizing: border-box;color: rgb(0, 85, 170)">$end</span>; </span><br></br><span style="box-sizing: border-box;padding-right: 0.1px">    <span style="box-sizing: border-box;color: rgb(170, 85, 0)">// 将数组第一值作为基准数</span></span><br></br><span style="box-sizing: border-box;padding-right: 0.1px">    <span style="box-sizing: border-box;color: rgb(0, 85, 170)">$pivot</span> <span style="box-sizing: border-box;color: rgb(152, 26, 26)">=</span> <span style="box-sizing: border-box;color: rgb(0, 85, 170)">$arr</span>[<span style="box-sizing: border-box;color: rgb(0, 85, 170)">$start</span>];</span><br></br><span style="box-sizing: border-box;padding-right: 0.1px"><span style="box-sizing: border-box"></span></span><br></br><span style="box-sizing: border-box;padding-right: 0.1px">    <span style="box-sizing: border-box;color: rgb(119, 0, 136)">while</span>(<span style="box-sizing: border-box;color: rgb(0, 85, 170)">$left</span> <span style="box-sizing: border-box;color: rgb(152, 26, 26)"><</span> <span style="box-sizing: border-box;color: rgb(0, 85, 170)">$right</span>) {</span><br></br><span style="box-sizing: border-box;padding-right: 0.1px">        <span style="box-sizing: border-box;color: rgb(170, 85, 0)">// 从右向左查找小于基准数的值</span></span><br></br><span style="box-sizing: border-box;padding-right: 0.1px">        <span style="box-sizing: border-box;color: rgb(119, 0, 136)">while</span>(<span style="box-sizing: border-box;color: rgb(0, 85, 170)">$left</span> <span style="box-sizing: border-box;color: rgb(152, 26, 26)"><</span> <span style="box-sizing: border-box;color: rgb(0, 85, 170)">$right</span> <span style="box-sizing: border-box;color: rgb(152, 26, 26)">&&</span> <span style="box-sizing: border-box;color: rgb(0, 85, 170)">$arr</span>[<span style="box-sizing: border-box;color: rgb(0, 85, 170)">$right</span>] <span style="box-sizing: border-box;color: rgb(152, 26, 26)">>=</span> <span style="box-sizing: border-box;color: rgb(0, 85, 170)">$pivot</span>) {</span><br></br><span style="box-sizing: border-box;padding-right: 0.1px">            <span style="box-sizing: border-box;color: rgb(170, 85, 0)">// 遍历数组元素，从右向左比较，直到找到小于基准值的数</span></span><br></br><span style="box-sizing: border-box;padding-right: 0.1px">            <span style="box-sizing: border-box;color: rgb(0, 85, 170)">$right</span><span style="box-sizing: border-box;color: rgb(152, 26, 26)">--</span>;</span><br></br><span style="box-sizing: border-box;padding-right: 0.1px">        }</span><br></br><span style="box-sizing: border-box;padding-right: 0.1px">        <span style="box-sizing: border-box;color: rgb(170, 85, 0)">// 找到小于基准值的后，与之互换位置</span></span><br></br><span style="box-sizing: border-box;padding-right: 0.1px">        <span style="box-sizing: border-box;color: rgb(0, 85, 170)">$arr</span>[<span style="box-sizing: border-box;color: rgb(0, 85, 170)">$left</span>] <span style="box-sizing: border-box;color: rgb(152, 26, 26)">=</span> <span style="box-sizing: border-box;color: rgb(0, 85, 170)">$arr</span>[<span style="box-sizing: border-box;color: rgb(0, 85, 170)">$right</span>];</span><br></br><span style="box-sizing: border-box;padding-right: 0.1px">        </span><br></br><span style="box-sizing: border-box;padding-right: 0.1px"><span style="box-sizing: border-box"></span></span><br></br><span style="box-sizing: border-box;padding-right: 0.1px">        <span style="box-sizing: border-box;color: rgb(170, 85, 0)">// // 从左向右查找小于基准数的值</span></span><br></br><span style="box-sizing: border-box;padding-right: 0.1px">        <span style="box-sizing: border-box;color: rgb(119, 0, 136)">while</span> (<span style="box-sizing: border-box;color: rgb(0, 85, 170)">$left</span> <span style="box-sizing: border-box;color: rgb(152, 26, 26)"><</span> <span style="box-sizing: border-box;color: rgb(0, 85, 170)">$right</span> <span style="box-sizing: border-box;color: rgb(152, 26, 26)">&&</span> <span style="box-sizing: border-box;color: rgb(0, 85, 170)">$arr</span>[<span style="box-sizing: border-box;color: rgb(0, 85, 170)">$left</span>] <span style="box-sizing: border-box;color: rgb(152, 26, 26)"><=</span> <span style="box-sizing: border-box;color: rgb(0, 85, 170)">$pivot</span>) {</span><br></br><span style="box-sizing: border-box;padding-right: 0.1px">            <span style="box-sizing: border-box;color: rgb(170, 85, 0)">// 遍历数组元素，从左向左向较，直到找到大于基准值的数</span></span><br></br><span style="box-sizing: border-box;padding-right: 0.1px">            <span style="box-sizing: border-box;color: rgb(0, 85, 170)">$left</span><span style="box-sizing: border-box;color: rgb(152, 26, 26)">++</span>;</span><br></br><span style="box-sizing: border-box;padding-right: 0.1px">        }</span><br></br><span style="box-sizing: border-box;padding-right: 0.1px">        <span style="box-sizing: border-box;color: rgb(170, 85, 0)">// 找到大于基准值的后，与之互换位置</span></span><br></br><span style="box-sizing: border-box;padding-right: 0.1px">        <span style="box-sizing: border-box;color: rgb(0, 85, 170)">$arr</span>[<span style="box-sizing: border-box;color: rgb(0, 85, 170)">$right</span>] <span style="box-sizing: border-box;color: rgb(152, 26, 26)">=</span> <span style="box-sizing: border-box;color: rgb(0, 85, 170)">$arr</span>[<span style="box-sizing: border-box;color: rgb(0, 85, 170)">$left</span>];</span><br></br><span style="box-sizing: border-box;padding-right: 0.1px">    }</span><br></br><span style="box-sizing: border-box;padding-right: 0.1px">    <span style="box-sizing: border-box;color: rgb(170, 85, 0)">// 交换基准值</span></span><br></br><span style="box-sizing: border-box;padding-right: 0.1px">    <span style="box-sizing: border-box;color: rgb(0, 85, 170)">$arr</span>[<span style="box-sizing: border-box;color: rgb(0, 85, 170)">$right</span>] <span style="box-sizing: border-box;color: rgb(152, 26, 26)">=</span> <span style="box-sizing: border-box;color: rgb(0, 85, 170)">$pivot</span>;</span><br></br> <br></br><span style="box-sizing: border-box;padding-right: 0.1px">    <span style="box-sizing: border-box;color: rgb(170, 85, 0)">// 再次递归调用</span></span><br></br><span style="box-sizing: border-box;padding-right: 0.1px">    <span style="box-sizing: border-box;color: rgb(0, 0, 0)">quick_sort_two</span>(<span style="box-sizing: border-box;color: rgb(0, 85, 170)">$arr</span>, <span style="box-sizing: border-box;color: rgb(0, 85, 170)">$start</span>, <span style="box-sizing: border-box;color: rgb(0, 85, 170)">$right</span><span style="box-sizing: border-box;color: rgb(152, 26, 26)">-</span><span style="box-sizing: border-box;color: rgb(17, 102, 68)">1</span>);</span><br></br><span style="box-sizing: border-box;padding-right: 0.1px">    <span style="box-sizing: border-box;color: rgb(0, 0, 0)">quick_sort_two</span>(<span style="box-sizing: border-box;color: rgb(0, 85, 170)">$arr</span>, <span style="box-sizing: border-box;color: rgb(0, 85, 170)">$right</span><span style="box-sizing: border-box;color: rgb(152, 26, 26)">+</span><span style="box-sizing: border-box;color: rgb(17, 102, 68)">1</span>, <span style="box-sizing: border-box;color: rgb(0, 85, 170)">$end</span>);</span><br></br><span style="box-sizing: border-box;padding-right: 0.1px">    <span style="box-sizing: border-box;color: rgb(119, 0, 136)">return</span> <span style="box-sizing: border-box;color: rgb(0, 85, 170)">$arr</span>;</span><br></br><span style="box-sizing: border-box;padding-right: 0.1px">}</span><br></br><span style="box-sizing: border-box;padding-right: 0.1px"><span style="box-sizing: border-box"></span></span><br></br><span style="box-sizing: border-box;padding-right: 0.1px"><span style="box-sizing: border-box"></span></span><br></br><span style="box-sizing: border-box;padding-right: 0.1px"><span style="box-sizing: border-box;color: rgb(0, 85, 170)">$arr</span> <span style="box-sizing: border-box;color: rgb(152, 26, 26)">=</span> [<span style="box-sizing: border-box;color: rgb(17, 102, 68)">5</span>,<span style="box-sizing: border-box;color: rgb(17, 102, 68)">11</span>,<span style="box-sizing: border-box;color: rgb(17, 102, 68)">1</span>,<span style="box-sizing: border-box;color: rgb(17, 102, 68)">6</span>,<span style="box-sizing: border-box;color: rgb(17, 102, 68)">10</span>];</span><br></br><span style="box-sizing: border-box;padding-right: 0.1px"><span style="box-sizing: border-box"></span></span><br></br><span style="box-sizing: border-box;padding-right: 0.1px"><span style="box-sizing: border-box;color: rgb(170, 85, 0)">// 计算程序运行的时间（微秒）</span></span><br></br><span style="box-sizing: border-box;padding-right: 0.1px"><span style="box-sizing: border-box;color: rgb(0, 85, 170)">$startTime</span> <span style="box-sizing: border-box;color: rgb(152, 26, 26)">=</span> <span style="box-sizing: border-box;color: rgb(51, 0, 170)">microtime</span>(<span style="box-sizing: border-box;color: rgb(34, 17, 153)">true</span>);</span><br></br><span style="box-sizing: border-box;padding-right: 0.1px"><span style="box-sizing: border-box;color: rgb(0, 85, 170)">$a</span> <span style="box-sizing: border-box;color: rgb(152, 26, 26)">=</span> <span style="box-sizing: border-box;color: rgb(0, 0, 0)">quick_sort_two</span>(<span style="box-sizing: border-box;color: rgb(0, 85, 170)">$arr</span>,<span style="box-sizing: border-box;color: rgb(17, 102, 68)">0</span>,<span style="box-sizing: border-box;color: rgb(51, 0, 170)">intval</span>((<span style="box-sizing: border-box;color: rgb(51, 0, 170)">count</span>(<span style="box-sizing: border-box;color: rgb(0, 85, 170)">$arr</span>)<span style="box-sizing: border-box;color: rgb(152, 26, 26)">-</span><span style="box-sizing: border-box;color: rgb(17, 102, 68)">1</span>)));</span><br></br><span style="box-sizing: border-box;padding-right: 0.1px"><span style="box-sizing: border-box;color: rgb(51, 0, 170)">print_r</span>(<span style="box-sizing: border-box;color: rgb(0, 85, 170)">$a</span>);</span><br></br><span style="box-sizing: border-box;padding-right: 0.1px"><span style="box-sizing: border-box;color: rgb(0, 85, 170)">$endTime</span> <span style="box-sizing: border-box;color: rgb(152, 26, 26)">=</span> <span style="box-sizing: border-box;color: rgb(51, 0, 170)">microtime</span>(<span style="box-sizing: border-box;color: rgb(34, 17, 153)">true</span>);</span><br></br><span style="box-sizing: border-box;padding-right: 0.1px"><span style="box-sizing: border-box;color: rgb(119, 0, 136)">echo</span> <span style="box-sizing: border-box;color: rgb(0, 85, 170)">$endTime</span> <span style="box-sizing: border-box;color: rgb(152, 26, 26)">-</span> <span style="box-sizing: border-box;color: rgb(0, 85, 170)">$startTime</span>;</span>

看运行结果

<span style="box-sizing: border-box;padding-right: 0.1px"><span style="box-sizing: border-box;color: rgb(0, 0, 0)">Array</span> ( [<span style="box-sizing: border-box;color: rgb(17, 102, 68)">0</span>] <span style="box-sizing: border-box;color: rgb(152, 26, 26)">=></span> <span style="box-sizing: border-box;color: rgb(17, 102, 68)">1</span> [<span style="box-sizing: border-box;color: rgb(17, 102, 68)">1</span>] <span style="box-sizing: border-box;color: rgb(152, 26, 26)">=></span> <span style="box-sizing: border-box;color: rgb(17, 102, 68)">5</span> [<span style="box-sizing: border-box;color: rgb(17, 102, 68)">2</span>] <span style="box-sizing: border-box;color: rgb(152, 26, 26)">=></span> <span style="box-sizing: border-box;color: rgb(17, 102, 68)">6</span> [<span style="box-sizing: border-box;color: rgb(17, 102, 68)">3</span>] <span style="box-sizing: border-box;color: rgb(152, 26, 26)">=></span> <span style="box-sizing: border-box;color: rgb(17, 102, 68)">10</span> [<span style="box-sizing: border-box;color: rgb(17, 102, 68)">4</span>] <span style="box-sizing: border-box;color: rgb(152, 26, 26)">=></span> <span style="box-sizing: border-box;color: rgb(17, 102, 68)">11</span> ) <span style="box-sizing: border-box;color: rgb(17, 102, 68)">1.2874603271484E-5</span></span><br></br><span style="box-sizing: border-box;padding-right: 0.1px">    </span><br></br><span style="box-sizing: border-box;padding-right: 0.1px"><span style="box-sizing: border-box;color: rgb(0, 0, 0)">Array</span> ( [<span style="box-sizing: border-box;color: rgb(17, 102, 68)">0</span>] <span style="box-sizing: border-box;color: rgb(152, 26, 26)">=></span> <span style="box-sizing: border-box;color: rgb(17, 102, 68)">1</span> [<span style="box-sizing: border-box;color: rgb(17, 102, 68)">1</span>] <span style="box-sizing: border-box;color: rgb(152, 26, 26)">=></span> <span style="box-sizing: border-box;color: rgb(17, 102, 68)">5</span> [<span style="box-sizing: border-box;color: rgb(17, 102, 68)">2</span>] <span style="box-sizing: border-box;color: rgb(152, 26, 26)">=></span> <span style="box-sizing: border-box;color: rgb(17, 102, 68)">6</span> [<span style="box-sizing: border-box;color: rgb(17, 102, 68)">3</span>] <span style="box-sizing: border-box;color: rgb(152, 26, 26)">=></span> <span style="box-sizing: border-box;color: rgb(17, 102, 68)">10</span> [<span style="box-sizing: border-box;color: rgb(17, 102, 68)">4</span>] <span style="box-sizing: border-box;color: rgb(152, 26, 26)">=></span> <span style="box-sizing: border-box;color: rgb(17, 102, 68)">11</span> ) <span style="box-sizing: border-box;color: rgb(17, 102, 68)">9.0599060058594E-6</span></span>

可以看到，多次刷新，排序所花费的时间不一样。

快速排序是一种不稳定的排序算法。

下面对快速排序进行图解

我是温新，每天进步一点点，就一点点。