写出一种排序算法(要写出代码),并说出优化它的方法。(新浪面试题)

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