概念

快速排序基于分治思想来实现。

  1. 分解:数组A[start,end]被划分为两个(可能为空)子数组A[start,postion-1]和A[postion+1,end]中的,使A[start,postion-1]的每一个元素都小于等于A[postion],A[postion+1,end]的每一个元素都大于等于A[postion]。
  2. 解决:通过递归调用快速排序,对子数组A[start,postion-1]和A[postion+1,end]进行排序。
  3. 合并:因为数组是原址排序,因此A[start,end]是有序的。

数组的划分(解决)实现思想图

PHP实现快速排序

function quickSort(&$array,$start,$end)
{
    if ($start < $end) {
        $postion = partition($array, $start, $end);
        quickSort($array,$start,$postion-1);
        quickSort($array,$postion+1,$end);
    }
}

function partition(&$arr,$start,$end) {
    $flag = $arr[$end];
    $i = $start-1;
    for ( $j=$start; $j<= $end-1; $j++) {
        if($arr[$j] <= $flag) {
            $i = $i+1;
            swap($arr,$i,$j);
        }
    }
    swap($arr,$i+1,$end);

    return $i+1;
}

function swap (&$arr,$exist,$replace) {
    $temp = $arr[$exist];
    $arr[$exist] = $arr[$replace];
    $arr[$replace] = $temp;
}

$array = array(1,6,5,4);
quickSort($array,0,3);
var_dump($array);