钛节点

排序篇之快速排序之入门篇

发表@2018-09-13 09:15:22

更新@2023-01-21 22:47:40

没吃过猪肉，总得见过猪跑。快速排序之所以这么被众所周知，除了性能略屌之外，还因为面试必备所以为大家所知。

![](https://ti-node.com/static/upload/6415151902215897088)

标题叫做入门篇，因为快排其实内含的原理和思想很深邃也很多，分治和递归都是有所体现的。快排的主题中心思想就是首先选中一个基准数（不作死的话，我建议你选中间那个），然后将剩余的挨个和基准数比大小，凡是比基准数大的放到一侧，凡是比基准数小的放到另一侧，然后再对这两侧的数据集重复上面的操作。一波儿操作猛如虎后，数据就能被按照一定顺序排好了。

所以，一般说来，可以尝试通过递归来解决一下核心问题，你们感受一下：

```php
<?php
$arr = [ 345,23,567,345345,234,122322,5464657,23423 ];
function quick( array $arr ){
  $length = count( $arr );
  if( 1 == $length ){
    return $arr;
  }
  // 位运算，不明白的同学自己补充下  >> 的含义
  $mid_index = $length >> 1;
  $left = [];
  $right = [];
  for( $i = 0; $i < $length; $i++ ){
    if( $i == $mid_index ){
      continue;
    }   
    // 如果比基准数大
    if( $arr[ $i ] > $arr[ $mid_index ] ){
        $right[] = $arr[ $i ];
    }   
    // 如果比基准数小
    else if( $arr[ $i ] < $arr[ $mid_index ] ){
      $left[] = $arr[ $i ];
    }   
  }
  return array_merge( $left, array( $arr[ $mid_index ] ), $right );
}
print_r( quick( $arr ) );
```

运行一下，你们看到结果如下：

![](https://ti-node.com/static/upload/6415155388433301505)

嗯，是的，上述代码有问题，我故意这么干的。实际上，有为青年大概能看出来这是将数组以234为基准数进行了一轮排列，所以比234小的都已经到前排变成了left数组，比234大的都到后排变成了right数组。但是，left和right数组本身却依旧是乱序的，那么下一步要做的就是对left和right也进行相同的操作即可！

所以，修改上述代码：

```php
<?php
$arr = [ 345,23,567,345345,234,122322,5464657,23423 ];
function quick( array $arr ){
  $length = count( $arr );
  if( $length <= 1 ){
    return $arr;
  }
  // 位运算，不明白的同学自己补充下  >> 的含义
  $mid_index = $length >> 1;
  $left = [];
  $right = [];
  for( $i = 0; $i < $length; $i++ ){
    if( $i == $mid_index ){
      continue;
    }   
    // 如果比基准数大
    if( $arr[ $i ] > $arr[ $mid_index ] ){
      $right[] = $arr[ $i ];
    }   
    // 如果比基准数小
    else if( $arr[ $i ] < $arr[ $mid_index ] ){
      $left[] = $arr[ $i ];
    }   
  }
  return array_merge( quick( $left ), array( $arr[ $mid_index ] ), quick( $right ) );
}
print_r( quick( $arr ) );
```

其中，上述代码的第72行，请仔细品悟。比如我问个问题，是quick( $left )先执行？还是quick( $right )先执行？又或者，他们是一边递归一边merge还是等所有排完了再最后merge？