PHP实战中知识总结 / 排序算法 - 快速排序算法

快速排序算法是对冒泡排序算法的改进，其基本思想是通过设置一个初始的中间值，来将需要排序的数组分成3部分：小于中间值的左边数组，中间值，大于中间值的右边数组，使用递归用相同的方式来排序左边和右边，最后合并数组。

/**
* 快速排序算法
* @param array $arr 要排序的数组
* @return array 排好序的数组
*/
public function quick_sort($arr)
{
  $count = count($arr);
  if ($count < 2) {
    return $arr;
  }
  //创建临时数组，以基准值为分界线，大于基准值的放在右侧，小鱼基准值的放在左侧
  $leftArr = $rightArr = array();
  //基准值，一般取数组第一个元素
  $middle = $arr[0];
  //循环数组与基准值比较
  for ($i = 1; $i < $count; $i++) {
    if ($arr[$i] < $middle) {
      $leftArr[] = $arr[$i];
    } else {
      $rightArr[] = $arr[$i];
    }
  }
  //递归，将左右数组排序
  $leftArr = $this->quick_sort($leftArr);
  $rightArr = $this->quick_sort($rightArr);
  //将排好序的临时数组合并
  return array_merge($leftArr, array($middle), $rightArr);
}