快速排序原理

快速排序使用分治法实现，其思想是寻找基准点然后进行比较，小于基准点的数放到其左边，大于的数放到其右边。

正常的情况下，时间复杂度是O(nlogn)；最坏的情况其时间复杂度是 O(n2)。

分治法实现快速排序的步骤

• 1、从数列中挑出一个数作为基准元素，通常选择第一个或最后一个元素，也有选择中间的；
• 2、扫描数列，把基准元素作为比较对象，将数列分成两个数组，小于基准元素的数在其左边，大于基准元素的数在其右边；
• 3、使用同样的方式继续排序，完成后，基准元素位置在两个排序位置的中间。

手动解析理解

<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(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)">192</span>,<span style="box-sizing: border-box;color: rgb(17, 102, 68)">9</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)">291</span>,<span style="box-sizing: border-box;color: rgb(17, 102, 68)">49</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)">4</span>,<span style="box-sizing: border-box;color: rgb(17, 102, 68)">149</span>,<span style="box-sizing: border-box;color: rgb(17, 102, 68)">65</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)">12</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(17, 102, 68)">1</span>)<span style="box-sizing: border-box;color: rgb(0, 0, 0)">选第一个元素</span> <span style="box-sizing: border-box;color: rgb(17, 102, 68)">5</span> <span style="box-sizing: border-box;color: rgb(0, 0, 0)">作为基准元素；</span></span><br></br><span style="box-sizing: border-box;padding-right: 0.1px"><span style="box-sizing: border-box;color: rgb(17, 102, 68)">2</span>)<span style="box-sizing: border-box;color: rgb(0, 0, 0)">基准元素5和数组中和所有元素进行比较，小于5的放在左边，大于5的放在右边，得到如下数据</span>;</span><br></br><span style="box-sizing: border-box;padding-right: 0.1px">[<span style="box-sizing: border-box;color: rgb(17, 102, 68)">1</span>,<span style="box-sizing: border-box;color: rgb(17, 102, 68)">4</span>] [<span style="box-sizing: border-box;color: rgb(17, 102, 68)">192</span>,<span style="box-sizing: border-box;color: rgb(17, 102, 68)">9</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)">291</span>,<span style="box-sizing: border-box;color: rgb(17, 102, 68)">49</span>,<span style="box-sizing: border-box;color: rgb(17, 102, 68)">149</span>,<span style="box-sizing: border-box;color: rgb(17, 102, 68)">65</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)">12</span>]</span><br></br><span style="box-sizing: border-box;padding-right: 0.1px"><span style="box-sizing: border-box;color: rgb(17, 102, 68)">3</span>)<span style="box-sizing: border-box;color: rgb(0, 0, 0)">采用递归，再次比较</span></span>

代码实现

结合递归实现快速排序

<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)">* quick_sort 快速排序</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)">*</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</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</span>(<span style="box-sizing: border-box;color: rgb(119, 0, 136)">array</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 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)"> $arrayLength</span> <span style="box-sizing: border-box;color: rgb(152, 26, 26)">=</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><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)"> if</span> (<span style="box-sizing: border-box;color: rgb(0, 85, 170)">$arrayLength</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(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;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(17, 102, 68)">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(0, 85, 170)"> $leftArr</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 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)"> $rightArr</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 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)">* 注意，此处索引 $i是从1开始的，</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)">* 因此，索引从1开始</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)"> for</span> (<span style="box-sizing: border-box;color: rgb(0, 85, 170)">$i</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)">$i</span> <span style="box-sizing: border-box;color: rgb(152, 26, 26)"><</span> <span style="box-sizing: border-box;color: rgb(0, 85, 170)">$arrayLength</span>; <span style="box-sizing: border-box;color: rgb(0, 85, 170)">$i</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 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)">if</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)">$i</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)">$rightArr</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)">$i</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)">else</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)">$leftArr</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)">$i</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><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)"> $leftArr</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</span>(<span style="box-sizing: border-box;color: rgb(0, 85, 170)">$leftArr</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)"> $rightArr</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</span>(<span style="box-sizing: border-box;color: rgb(0, 85, 170)">$rightArr</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(119, 0, 136)"> return</span> <span style="box-sizing: border-box;color: rgb(51, 0, 170)">array_merge</span>(<span style="box-sizing: border-box;color: rgb(0, 85, 170)">$leftArr</span>, <span style="box-sizing: border-box;color: rgb(119, 0, 136)">array</span>(<span style="box-sizing: border-box;color: rgb(0, 85, 170)">$pivot</span>), <span style="box-sizing: border-box;color: rgb(0, 85, 170)">$rightArr</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)">$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)">192</span>,<span style="box-sizing: border-box;color: rgb(17, 102, 68)">9</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)">291</span>,<span style="box-sizing: border-box;color: rgb(17, 102, 68)">49</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)">4</span>,<span style="box-sizing: border-box;color: rgb(17, 102, 68)">149</span>,<span style="box-sizing: border-box;color: rgb(17, 102, 68)">65</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)">12</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(51, 0, 170)">print_r</span>(<span style="box-sizing: border-box;color: rgb(0, 0, 0)">quick_sort</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 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"></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(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)">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)">4</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)">5</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)">9</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)">10</span> [<span style="box-sizing: border-box;color: rgb(17, 102, 68)">5</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)">6</span>] <span style="box-sizing: border-box;color: rgb(152, 26, 26)">=></span> <span style="box-sizing: border-box;color: rgb(17, 102, 68)">12</span> [<span style="box-sizing: border-box;color: rgb(17, 102, 68)">7</span>] <span style="box-sizing: border-box;color: rgb(152, 26, 26)">=></span> <span style="box-sizing: border-box;color: rgb(17, 102, 68)">49</span> [<span style="box-sizing: border-box;color: rgb(17, 102, 68)">8</span>] <span style="box-sizing: border-box;color: rgb(152, 26, 26)">=></span> <span style="box-sizing: border-box;color: rgb(17, 102, 68)">65</span> [<span style="box-sizing: border-box;color: rgb(17, 102, 68)">9</span>] <span style="box-sizing: border-box;color: rgb(152, 26, 26)">=></span> <span style="box-sizing: border-box;color: rgb(17, 102, 68)">149</span> [<span style="box-sizing: border-box;color: rgb(17, 102, 68)">10</span>] <span style="box-sizing: border-box;color: rgb(152, 26, 26)">=></span> <span style="box-sizing: border-box;color: rgb(17, 102, 68)">192</span> [<span style="box-sizing: border-box;color: rgb(17, 102, 68)">11</span>] <span style="box-sizing: border-box;color: rgb(152, 26, 26)">=></span> <span style="box-sizing: border-box;color: rgb(17, 102, 68)">291</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(17, 102, 68)">1.1920928955078E-5</span></span>

由于第二种方法的理解难度略大于此文中的方法，为了更好的实现，将第二种方法独立成一篇文章，并配上图解，这样更为容易理解些。

2021-06-03更新

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