排序算法之快速排序

快速排序是一种基于分治策略的排序方法。其基本思想是：首先从待排序区间（初始时为[1..n]）中选取一个元素作为基准元素，然后从两端向中间依次进行比较和交换，把位于基准元素之前且比基准元素大的交换到后面，把位于基准元素之后且比基准元素小的交换到前面，而基准元素位于前后两部分的交界处。这样前面部分的所有元素都小于等于基准元素，后面部分的所有元素均大于等于基准元素，基准元素的当前位置就是排序后的最终位置。然后在对基准元素的前后两个区间分别进行快速排序，直至每个区间为空或只包含一个元素，整个快速排序结束。
快速排序根据选取基准元素位置的不同，分为取首快排，取中快排，随机快排。

代码是取首快排，即将第一个元素选为基准元素。

<?php

function quickSort($arr){

   $len = count($arr);

   if($len <= 1) {


       return $arr;
    }
 
  $key = $arr[0];
  
$left_arr = array();

   $right_arr = array();
 
  for($i=1; $i<$len; $i++){
  
     if($arr[$i] <= $key){
 
          $left_arr[] = $arr[$i];
 
      }
 
      else{
 
          $right_arr[] = $arr[$i];

       }
 
  }

   $left_arr = quickSort($left_arr);
 
  $right_arr = quickSort($right_arr);
 
  return array_merge($left_arr, array($key), $right_arr);

}

$arr = array(225,220,41,190,242,185,42,231);

print_r(quickSort($arr));

?>