1 <?php 2 //快速排序 3 function partition(&$arr, $low, $high) 4 { 5 $pivotkey = $arr[$low]; 6 while ($low < $high) { 7 while ($low < $high && $arr[$high] >= $pivotkey) { 8 $high--; 9 } 10 $temp = $arr[$low]; 11 $arr[$low] = $arr[$high]; 12 $arr[$high] = $temp; 13 while ($low < $high && $arr[$low] <= $pivotkey) { 14 $low++; 15 } 16 $temp = $arr[$low]; 17 $arr[$low] = $arr[$high]; 18 $arr[$high] = $temp; 19 } 20 return $low; 21 } 22 23 /** 24 * @param $arr 数组 25 * @param $low 数据排序 起始位置（下标） 26 * @param $high 数据排序 结束位置（下标） 27 */ 28 function quick_sort(&$arr, $low, $high) 29 { 30 if ($low < $high) { 31 $pivot = partition($arr, $low, $high); 32 quick_sort($arr, $low, $pivot - 1); 33 quick_sort($arr, $pivot + 1, $high); 34 } 35 } 36 37 $arr = array(10,9,8,7,6,5); 38 quick_sort($arr, 3,4); 39 echo '<pre>'; 40 foreach ($arr as $v) { 41 echo $v.'<br/>'; 42 }
该算法是通过分治递归来实现的，其效率很大程度上取决于参考元素的选择，可以选择数组的中间元素，也可以随机得到三个元素，然后选择中间的那个元素（三数中值法）。
另外还有一点，就是当我们在分割时，如果分割出来的子序列的长度很小的话（小于5到20），通常递归的排序的效率就没有诸如插入排序或希尔排序那么快了。因此可以会去判断数组的长度，如果小于10的话，直接用插入排序，而不再递归调用这个快速排序
如果本文章已帮助到您！
