一、定义

基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

通俗说就是数组中找出一个随机数（一般拿数组第一个数），把它插入一个位置，让它左边的数都比它小，右边的数都比它大，这样就将一个数组分成了两个字数组。然后再根据同样的方法递归，直到不能分解为止，这个时候数组就已经排好序了。

二、排序演示

下面演示了用第一个数字12将数组分成了两个数组。

取第一个数作为基准数，这是low=0，high=8，target=arr[0]=12，由于已经将arr[0]保存到变量target中，可以理解成在数组arr[0]上挖了一个坑，那就需要将这个坑填上，从high=8开始向后扫描，遇到一个比target小的数，arr[8]就符合，用arr[8]这个数将arr[0]这个坑填上，arr[0]=arr[8]；arr[8]又出现了坑，就需要从low=1开始由左向右扫描，找一个比target=12大的数，arr[1]就符合，将arr[8]的这个坑用arr[1]填上，arr[8]=arr[1]；arr[1]出现了坑，需要从high=7开始向左扫描，找一个比target=12小的数，arr[7]填上arr[1]，arr[1] = arr[7]；在由low=2开始向右扫描，找一个比target=12大的数，arr[2]填上arr[7]，arr[7]=arr[2]......直到high=low，将目标数填上最后的这个坑，arr[high]=target，这样就排好序了。

三、性能分析

①、快排的一个关键因素是选好枢轴，它进行一趟排序后，枢轴元素在表中的位置被唯一确定下来，且枢轴元素将待排序列分成两个子序列，左边的序列中的元素都比 枢轴元素小，右边的序列都比枢轴元素大。然后，分别在左右序列中选择枢轴元素再开始排序，因而，快排中包含了递归。

 ②、当待排的元素初始有序时，快排的性能大大地下降。因为此时枢轴划分的子序列严重地不对称（一般选择第一个元素作为枢轴记录），快排退化为冒泡排序。

③、快排是不稳定的，因为在排序过程中，设置了两个指针 low 和 high 。首先从high 开始自减，寻找第一个比枢轴小的元素，并将之与枢轴记录进行交换，这种跳跃式的交换可能会造成元素的相对位置的改变。

 ④、对于快排而言，元素的初始序列与排序的趟数和比较次数是有关的。但是，平均情况下，对于内部排序而言，快排的性能是最好。平均时间复杂度为 O（n^2)，空间复杂度为O（logn）。

四、代码实现

function InsertSort(array &$arr){
    $count = count($arr);
    //数组中第一个元素作为一个已经存在的有序表
    for($i = 1;$i < $count;$i ++){
        $temp = $arr[$i];   //设置哨兵
        for($j = $i - 1;$j >= 0 && $arr[$j] > $temp;$j --){
            $arr[$j + 1] = $arr[$j];    //记录后移
        }
        $arr[$j + 1] = $temp;   //插入到正确的位置
    }
}
$arr = array(9,1,5,8,3,7,4,6,2);
InsertSort($arr);
var_dump($arr);
var_dump(microtime());

或者

function quickSort($arr) {
        //先判断是否需要继续进行
        $length = count($arr);
        if($length <= 1) {
            return $arr;
        }
        //选择第一个元素作为基准
        $base_num = $arr[0];
        //遍历除了标尺外的所有元素，按照大小关系放入两个数组内
        //初始化两个数组
        $left_array = array();  //小于基准的
        $right_array = array();  //大于基准的
        for($i=1; $i<$length; $i++) {
            if($base_num > $arr[$i]) {
                //放入左边数组
                $left_array[] = $arr[$i];
            } else {
                //放入右边
                $right_array[] = $arr[$i];
            }
        }
        //再分别对左边和右边的数组进行相同的排序处理方式递归调用这个函数
        $left_array = $this->quickSort($left_array);
        $right_array = $this->quickSort($right_array);
        //合并
        return array_merge($left_array, array($base_num), $right_array);
    }