本文转载于 SegmentFault 社区
作者：七友
快速排序由 C. A. R. Hoare 在 1960 年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序。更多介绍可以百度百科，接下来直接上代码。
PHP 版本 V1.0
这个版本我看了之前有一篇 C 算法文章中的写法，应该算很早的版本了，我把他用 PHP 写了一版.递归部分我是使用替换的方式进行合并数据，也可以使用 PHP 引用(&) 进行合并。下面是代码和实现步骤：
/**
* PHP 快速排序 v1.0
* 实现步骤：
* 1.首先在数据中定义一个基准数(M)，具体怎么选因人而异。,定义好左右两个坐标L、R （左边坐标不能大于右边坐标）
* 2.定义好基准数(M)后，从最右往左找小于基准数(M)的值(J)并且不能小于或等于左边坐标,找到后停止。
* 3.再从左往右找大于基准数(M)的值(I)并且不能小于或等于右边坐标，找到后停止。（为什么要先从右往左？因为从左往右就会错过太多大于的值从而相遇，导致排序错乱）
* 4.I和J都找到后，进行交换位置。
* 5.重复1-4步骤直到两个数相同的值(V)，则将V和M互换位置。
* 6.再以M为中心点进行分割重复1-5的流程直至结束
* @param array $data 数据
* @param int $left 左边坐标
* @param int $right 右边坐标
* @param string $orderBy 正序/倒叙
* @return array $data
*/
function QuickSort($data, $left, $right, $orderBy = 'asc')
{
$l = $left; // 左边开始位置
$r = $right; // 右边开始位置
if ($left >= $right) return [];
$m = $data[$left]; // 基准数
while ($l != $r) {
while ($data[$r] >= $m && $r != $l) $r--;
while ($data[$l] <= $m && $r != $l) $l++;
if ($l < $r) {
$n = $data[$l];
$data[$l] = $data[$r];
$data[$r] = $n;
}
}
$data[$left] = $data[$l];
$data[$l] = $m;
$Q1 = QuickSort($data, $left, $l - 1, $orderBy);
$data = $Q1 + $data;
$Q2 = QuickSort($data, $l + 1, $right);
$data = $Q2 + $data;
return $data;
}
PHP 版本 V2.0（推荐）
这个版本就很流弊了，比上面写法快的太多太多，犹如一个天一个地。我拿第一个版本去对比发现差得太多了。我用 v1 版本写法执行 10000 就消耗 10s 左右，而用 v2 这个写法直接秒开。不管哪种语言，实现逻辑都一样，推荐参考：
/**
* 快速排序 v2.0
* 实现步骤：
* 1.建立基准数（中间值）
* 2.循环数据，大于基准数的存 right 数组，小于基准数的存 left 数组
* 3.分类完成后，将 left、right 数组递归继续分类，直至剩下一个数组为止
* 4.递归分类完成后，将小于基准数的数组 left 、 基准数 和 大于基准数的数组 进行合并
* @param array $data
* @return array
*/
function QuickSort($data)
{
$left = [];
$right = [];
$count = count($data);
if ($count < 2) return $data;
$median = $data[0]; // 基准数
for ($i = 1; $i < $count; $i++) {
$v = $data[$i];
if ($v < $median) $left[] = $v; else $right[] = $v;
}
$left = QuickSort($left);
$right = QuickSort($right);
$rt = array_merge($left, [$median], $right);
return $rt;
}
C 语言版本
接下来就是 C 语言的快速排序版本 V1.0
(我第一次使用的快速排序思想，自己定义的版本号来区分下~^_^)
稍微改动了一下。
#include
#include
int a[101],n;
/**
* C语言实现快速排序v1.0
*/
void quicksort(int left, int right){
int i,j,base;
i = left;
j = right;
if (left>right) return ;
// 1.第一步，定义基准数
base = a[left];
// 4.左坐标不等于右坐标时继续迭代，等于则相遇
while(left != right){
// 2.如果右边大于基准数则继续递减迭代至小于基准数停止
while(left<right && a[right]>=base) right--;
// 2.1 与左指针所在位置进行交换
a[left] = a[right];
// 3.如果左边小于基准数则继续递增迭代至大于基准数停止
while(left<right && a[left]<=base) left++;
// 3.1 与右指针所在位置进行交换
a[right] = a[left];
}
// 4.1 左右坐标相遇替换基准数
a[left] = base;
// 5.重复1.2.3.4 递归
quicksort(i, left-1); // 重复基准数左边
quicksort(left+1, j);
return;
}
int main()
{
int i,j;
printf("=============快速排序==============\r\n");
printf("请输入数量：");
scanf("%d", &n);
for (i=1; i<=n; i++){
scanf("%d", &a[i]);
}
quicksort(1, n);
printf("快速排序结果：\r\n");
for (i=1; i<=n; i++)
printf("%d ", a[i]);
getchar(); getchar();
system("pause");
return 0;
}
Javascript 语言版本
这个在网上找到的，和 v2 的版本实现思想一致：
