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

一、快速排序法

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;

\$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;

\$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, )