首页 > > 网络编程 > Php编程 >

写出一种排序算法（要写出代码），并说出优化它…

2018-06-29 06:07:15来源：博客园阅读 ()

 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的话，直接用插入排序，而不再递归调用这个快速排序。

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有