基本思想:选择一个基准元素,通常选择第一个元素,通过一趟扫描,将待排序列分为两个部分,一部分比基准元素小(做数组),一部分大于等于基准元素组(右数组),此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。
可以看到,这种方法是把大问题转变为小问题的方法,使用递归实现。
<?php //递归函数的特点有两个 //1.要有递归出口,应该放到递归函数的最前面 //2.要有递归调用 function quick sort ($arr) { //递归出口判断要放在最前面 if (count($arr) <= 1){ return $arr; } //把第一个元素从数组中弹出去放在一个变量中 $key = array_shift($arr); //把刚才弹出的第一个元素(基准元素)存到一个数组中 $key_arr = array($key); //定义两个空数组,给左边和右边的数组进行初始化。 $left_arr = array(); $right_arr = array(); foreach ($arr as $value){ if($value < $key){ $left_arr[] = $value; }else{ $right_arr[] = $value; } } //这里就是递归调用 return array_merge(quick_sort($left_arr), $key_arr, quick_sort($right_arr)); }