1. 概述

思路：数组排序中，选取数组末尾的一个数叫作轴，初始一左一右指针分别都往序列中间位置逐步移动，比轴小的不动，比轴大的数与轴往前的位置的数交换值，完成后让轴与右指针交换位置，这样就完成了一次大小数字以轴为界限分成两部分了。再对当前序进行递归二分至1个元素，完成完成上述排序过程。
稳定性：不稳定（在一次排序中，可能出现左边的大数（存在相同指）交换到相同值的右边去，比如序列：[1834825] -> [1234885]，在交换$arr[1]和$arr[5]时，对于原序，前面的8跑到右边的8的后面去了）

优化：1. 随机选择一个数与末尾数交换（这样可以减少原序已经是顺序的情况，因为顺序的时候时间复杂度最大）2. 双轴快排

2. 实现代码

```php <?php class QuickSort { private array $ori = []; public array $new = []; public function __construct(array $arr) {

  $this->ori = $arr;
  $r = $this->sort($this->ori, 0, count($arr) - 1);
  $this->new = $r;

}

private function sort(array $arr, int $lBd, int $rBd) {

  if ($lBd >= $rBd) return $arr;

  list($arr, $mid) = $this->partition($arr, $lBd, $rBd);
  $arr = $this->sort($arr, $lBd, $mid - 1);
  $arr = $this->sort($arr, $mid + 1, $rBd);
  return $arr;

}

private function partition($arr, $lBd, $rBd) {

  $pivot = $arr[$rBd];
  $left = $lBd;
  $right = $rBd - 1;

  // 防止最差情况（最差的时间复杂度是n^2）
  if ($right > $left + 1) {
      self::swap($arr, $right, floor(($right - $left) / 2) + 1);
  }

  while($left <= $right) {
      while ($left <= $right && $arr[$left] <= $pivot) $left++;
      while ($left <= $right && $arr[$right] > $pivot) $right--;
      if ($left < $right) {
          $arr = self::swap($arr, $left, $right);
      }
  }
  $arr = self::swap($arr, $left, $rBd);
  return [$arr, $left];

}

public static function swap(array $arr, int $i, int $j) {

  $tmp = $arr[$i];
  $arr[$i] = $arr[$j];
  $arr[$j] = $tmp;
  return $arr;

} }

$arr = [9, 6, 11, 3, 5, 12, 8, 7, 10, 15, 14, 4, 1, 13, 2]; $cls = new QuickSort($arr); echo implode(‘,’, $cls->new); ```

常用经典算法

快速排序

1. 概述

2. 实现代码