快速排序

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

1. 算法描述

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

• 从数列中挑出一个元素，称为 “基准”（pivot）；
• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
• 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

2. 动图演示

image

3. 代码实现

<?php
//输出数组序列
function echo_arr($arr, $sym=' '){
    echo implode($sym, $arr).'<br>';
}

function quick_sort($arr){
    $len = count($arr);
    if($len <= 1){
        return $arr;
    }
   
    //基准  
    $point = $arr[$len >> 1];
    $left_arr = array();  
    $right_arr = array(); 
 
    for($i=0; $i<$len; $i++){
        if($arr[$i] == $point){
            continue;
        }

        if($arr[$i] < $point){  
            $left_arr[] = $arr[$i];  
        }
        else if($arr[$i] > $point){  
            $right_arr[] = $arr[$i];  
        }  
    }

    //递归排序左半部分
    $left_arr = quick_sort($left_arr);  
    //递归排序右半部分
    $right_arr = quick_sort($right_arr);

    //合并左半部分、基准、右半部分   
    return array_merge($left_arr, array($point), $right_arr);
}

$arr = array(9,5,32,16,9,22,66,45,99,55);
echo_arr($arr);
$sort_arr = quick_sort($arr);
echo_arr($sort_arr);