快速排序法通过设置一个中间值,把要排序的数组进行递归,如果按从小到大排序,小于中间值的放左边,中间值在中间,大于中间值的放右边,最后合并数组得出的结果。

  一、快速排序法

  php

  $arr = [11, 3, 10, 8, 7, 4, 2, 1, 9, 3, 5, 15];

  class quickSort

  {

  public static function qSort($arr)

  {

  if (count($arr) <= 1) {

  return $arr;

  }

  // 中间值

  $middle = $arr[0];

  $left = $right = [];

  foreach ($arr as $key => $val) {

  if ($key == 0) {

  continue;

  }

  if ($val > $middle) {

  $right[] = $val;

  } else {

  $left[] = $val;

  }

  }

  $left = self::qSort($left, $n);

  $right = self::qSort($right, $n);

  return array_merge($left, [$middle], $right);

  }

  }

  var_export(quickSort::qSort($arr));

  执行结果:

  php

  array ( 0 => 1, 1 => 2, 2 => 3, 3 => 3, 4 => 4, 5 => 5, 6 => 7, 7 => 8, 8 => 9, 9 => 10, 10 => 11, 11 => 15, )

  二、运行过程

  加入对每次数据的记录,查看每次的排序流程。

  php

  $arr = [11, 3, 10, 8, 7, 4, 2, 1, 9, 3, 5, 15];

  echo var_export($arr) . "

  ";

  class quickSort

  {

  public static function qSort($arr, $n)

  {

  if (count($arr) <= 1) {

  return $arr;

  }

  // 中间值

  $middle = $arr[0];

  $left = $right = [];

  foreach ($arr as $key => $val) {

  if ($key == 0) {

  continue;

  }

  if ($val > $middle) {

  $right[] = $val;

  } else {

  $left[] = $val;

  }

  }

  $n++;

  $left = self::qSort($left, $n);

  echo '第' . $n . '次(left)' . "

  " . var_export($left);

  $right = self::qSort($right, $n);

  echo '第' . $n . '次(right)' . "

  " . var_export($right);

  echo '第' . $n . '次(all)' . "

  " . var_export(array_merge($left, [$middle], $right));

  return array_merge($left, [$middle], $right);

  }

  }

  var_export(quickSort::qSort($arr, $n = 0));

  执行结果:

  php

  array ( 0 => 11, 1 => 3, 2 => 10, 3 => 8, 4 => 7, 5 => 4, 6 => 2, 7 => 1, 8 => 9, 9 => 3, 10 => 5, 11 => 15, )

  array ( 0 => 1, )第3次(left)

  array ( 0 => 3, )第3次(right)

  array ( 0 => 1, 1 => 2, 2 => 3, )第3次(all)

  array ( 0 => 1, 1 => 2, 2 => 3, )第2次(left)

  array ( )第6次(left)

  array ( 0 => 5, )第6次(right)

  array ( 0 => 4, 1 => 5, )第6次(all)

  array ( 0 => 4, 1 => 5, )第5次(left)

  array ( )第5次(right)

  array ( 0 => 4, 1 => 5, 2 => 7, )第5次(all)

  array ( 0 => 4, 1 => 5, 2 => 7, )第4次(left)

  array ( 0 => 9, )第4次(right)

  array ( 0 => 4, 1 => 5, 2 => 7, 3 => 8, 4 => 9, )第4次(all)

  array ( 0 => 4, 1 => 5, 2 => 7, 3 => 8, 4 => 9, )第3次(left)

  array ( )第3次(right)

  array ( 0 => 4, 1 => 5, 2 => 7, 3 => 8, 4 => 9, 5 => 10, )第3次(all)

  array ( 0 => 4, 1 => 5, 2 => 7, 3 => 8, 4 => 9, 5 => 10, )第2次(right)

  array ( 0 => 1, 1 => 2, 2 => 3, 3 => 3, 4 => 4, 5 => 5, 6 => 7, 7 => 8, 8 => 9, 9 => 10, )第2次(all)

  array ( 0 => 1, 1 => 2, 2 => 3, 3 => 3, 4 => 4, 5 => 5, 6 => 7, 7 => 8, 8 => 9, 9 => 10, )第1次(left)

  array ( 0 => 15, )第1次(right)

  array ( 0 => 1, 1 => 2, 2 => 3, 3 => 3, 4 => 4, 5 => 5, 6 => 7, 7 => 8, 8 => 9, 9 => 10, 10 => 11, 11 => 15, )第1次(all)

  array ( 0 => 1, 1 => 2, 2 => 3, 3 => 3, 4 => 4, 5 => 5, 6 => 7, 7 => 8, 8 => 9, 9 => 10, 10 => 11, 11 => 15, )