快速排序

思路分析:

  选择一个基准元素,通常选择第一个元素或者最后一个元素。通过一遍扫描,将待排序数组分成两部分,一部分比基准元素小,一部分大于等于基准元素。此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分

 1 //快速排序
 2 function quickSort($arr)
 3 {
 4     $len = count($arr);
 5     if ($len <= 1) {
 6         return $arr;
 7     }
 8     $base = $arr[0];
 9     $left_arr = [];
10     $right_arr = [];
11     for ($i = 1; $i < $len; $i++) {
12         if ($base > $arr[$i]) {
13             $left_arr[] = $arr[$i];
14         } else {
15             $right_arr[] = $arr[$i];
16         }
17     }
18     $left_arr = quickSort($left_arr);
19     $right_arr = quickSort($right_arr);
20     return array_merge($left_arr, array($base), $right_arr);
21 }

$arr = [3, 2, 8, 6, 7, 5, 9, 4, 1];
$new_arr = quickSort($arr);
print_r($new_arr);

 

上一篇:C模板不接受迭代器


下一篇:算法设计与分析(三)分治法--快速排序的递归和非递归实现