快速排序

选择一个基准元素，通常选择第一个元素或者最后一个元素。通过一趟扫描，将待排序列分成两部分，一部分比基准元素小，一部分大于等于基准元素。此时基准元素在其排好序后的正确位置，然后再用同样的方法递归地排序划分的两部分
时间复杂度：O(nlogN) 最差：O(n2)

方法一

<?php
/**
* 快速排序.
  * @param  array $value 待排序数组
  * @param  array $left  左边界
  * @param  array $right 右边界
  * @return array
  */
function quick(&$value, $left, $right) {
    //左右边界重合，跳出
    if ($left >= $right) {
        return;
    }
    //左边的设为基准数
    $base = $left;
    //执行
    do {
        // 从最右边开始找到第一个比基准小的值，互换位置
        // 找到基准索引为止
        for ($i=$right; $i > $base; --$i) {
            if ($value[$i] < $value[$base]) {
                $tmp = $value[$i];
                $value[$i] = $value[$base];
                $value[$base] = $tmp;
                $base = $i; // 更新基准值索引
                break;
            }
        }
        // 从最左边开始找到第一个比基准大的值，互换位置
        // 找到基准索引为止
        for ($j=$left; $j < $base; ++$j) {
            if ($value[$j] > $value[$base]) {
                $tmp = $value[$j];
                $value[$j] = $value[$base];
                $value[$base] = $tmp;
                $base = $j; // 更新基准值索引
                break;
            }
        }
    } while($i > $j);//直到左右索引重合为止
    // 开始递归
    // 以当前索引为分界
    // 开始排序左部分
    quick($value, $left, $i-1);
    // 开始排序右边部分
    quick($value, $i+1, $right);
    return $value;
}
    

方法二

<?php
   /**
   * 快速排序.while版本
   * @param  array $value 待排序数组
   * @param  array $left  左边界
   * @param  array $right 右边界
   * @return array
   */
function quick_while(&value, $left, $right) {
    if ($left >= $right) {
        return;
    }
    $point = $left;
    $i = $right;
    $j = $left;
    //查右边值
    while ($i > $j) {
        if ($value[$i] < $value[$point]) {
            $tmp = $value[$i];
            $value[$i] = $value[$point];
            $value[$point] = $tmp;
            $point = $i;
            break;
        }
        --$i;
    }
    //查左边值
    while ($j < $point) {
        if ($value[$j] > $value[$point]) {
            $tmp = $value[$j];
            $value[$j] = $value[$point];
            $value[$point] = $tmp;
            $point = $j;
            break;
        }
        ++$j;
    }
    // 开始递归
    // 以当前索引为分界
    // 开始排序左部分
    quick_while($value, $left, $i-1);
    // 开始排序右边部分
    quick_while($value, $i+1, $right);
    return $value;
}