一、前言
快速排序是一种交换排序，它由C. A. R. Hoare在1962年提出。
二、算法思想
快速排序的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分：分割点左边都是比它小的数，右边都是比它大的数。
然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
动态效果示意图：
详细的图解往往比大堆的文字更有说明力，所以直接上图：
上图中，演示了快速排序的处理过程：
初始状态为一组无序的数组：2、4、5、1、3。
经过以上操作步骤后，完成了第一次的排序，得到新的数组：1、2、5、4、3。
新的数组中，以2为分割点，左边都是比2小的数，右边都是比2大的数。
因为2已经在数组中找到了合适的位置，所以不用再动。
2左边的数组只有一个元素1，所以显然不用再排序，位置也被确定。（注：这种情况时，left指针和right指针显然是重合的。因此在代码中，我们可以通过设置判定条件left必须小于right，如果不满足，则不用排序了）。
而对于2右边的数组5、4、3，设置left指向5，right指向3，开始继续重复图中的一、二、三、四步骤，对新的数组进行排序。
python 代码
# -*- coding:utf-8 -*-def QuickSort(input_list, left, right):'''函数说明:快速排序（升序）Author:www.cuijiahua.comParameters:input_list - 待排序列表Returns:无''' def division(input_list, left, right):'''函数说明:根据left和right进行一次扫描，重新找到基准数Author:www.cuijiahua.comParameters:input_list - 待排序列表left - 左指针位置right - 右指针位置Returns:left - 新的基准数位置''' base = input_list[left]while left < right:while left < right and input_list[right] >= base:right -= 1input_list[left] = input_list[right]while left < right and input_list[left] <= base:left += 1input_list[right] = input_list[left]input_list[left] = basereturn leftif left < right:base_index = division(input_list, left, right)QuickSort(input_list, left, base_index - 1)QuickSort(input_list, base_index + 1, right)if __name__ == '__main__':input_list = [6, 4, 8, 9, 2, 3, 1]print('排序前:', input_list)QuickSort(input_list, 0, len(input_list) - 1)print('排序后:', input_list)
php代码
1 递归实现
找到当前数组中的任意一个元素（一般选择第一个元素），作为标准，新建两个空数组，遍历整个数组元素，
如果遍历到的元素比当前的元素要小，那么就放到左边的数组，否则放到右面的数组，然后再对新数组进行同样的操作，
不难发现，这里符合递归的原理，所以我们可以用递归来实现。
使用递归，则需要找到递归点和递归出口：
递归点：如果数组的元素大于1，就需要再进行分解，所以我们的递归点就是新构造的数组元素个数大于1
递归出口：我们什么时候不需要再对新数组不进行排序了呢？就是当数组元素个数变成1的时候，所以这就是我们的出口。
<?php
/**
* Created by PhpStorm.
* User: brady
* Date: 2018/10/10
* Time: 11:33
*/
/**
* @author brady
* @desc 快速插入排序
* @param $arr 待排序的数组
* @param string $sort asc升序 desc降序
* @time 2018/10/10
*/
function quick_sort($arr,$sort='asc')
{
echo json_encode($arr);
echo "<hr>";
//递归出口:数组长度为1，直接返回数组
$length=count($arr);
if($length<=1) return $arr;
//数组元素有多个,则定义两个空数组
$left=$right=array();
//使用for循环进行遍历，把第一个元素当做比较的对象
for($i=1;$i<$length;$i++)
{
//判断当前元素的大小
if($sort == 'asc'){
if($arr[$i]<$arr[0]){
$left[]=$arr[$i];
}else{
$right[]=$arr[$i];
}
} else {
if($arr[$i] > $arr[0]){
$left[]=$arr[$i];
}else{
$right[]=$arr[$i];
}
}
}
//递归调用
$left=quick_sort($left,$sort);
$right=quick_sort($right,$sort);
//将所有的结果合并
return array_merge($left,array($arr[0]),$right);
}
$arr=array(6,3,8,6,4,2,9,5,1);
//调用
echo "<pre>";
print_r($arr);
print_r(quick_sort($arr,'desc'));
