曾经有一个人让我写下快排算法，我给他写出来了，然后就被Diss了，怎么申请这么多临时变量。来，各位看官一起看看本菜🐔的作业。各位看官也可以动手写一写。
快速排序的逻辑 — 来自百度百科
快速排序算法通过多次比较和交换来实现排序，其排序流程如下:
(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。
(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
<?php
$input = [100, 23, 452, 234, 56223, 6234, 134, 51, 234];
$ret = quickSort($input);
printf("%s\n", json_encode($ret));
function quickSort($input)
{
$len = count($input);
if ($len <= 1) {
return $input;
}
$temp = $input[0];
$left = $right = [];
for ($i = 1; $i < $len; $i++) {
if ($temp >= $input[$i]) {
$left[] = $input[$i];
} else {
$right[] = $input[$i];
}
}
$left = quickSort($left);
$right = quickSort($right);
return array_merge($left, [$temp], $right);
}
基本上也是符合快速排序的标准，不过确实$left和$right这两个属于数组copy，会需要大量的内存空间的。但是既然说到利用了中间变量来存放数组，那么是否有别的方式呢？
答案肯定是有的了，既然不能用中间变量存数组，那么我可以使用交换的方式，因为反正都是比大小，我们通过一个临时变量将原数组的数据挖一个出来，然后再去比较，可以看下面的示例。
[100, 23, 452, 234, 56223, 6234, 134, 51, 234]
第一趟，我先取100出来，然后从右向左扫描，比他小的（51<100）放入他的坑，那么结果如下：
[---, 23, 452, 234, 56223, 6234, 134, 51, 234]
从左扫发现51，填入左边的坑。
[51, 23, 452, 234, 56223, 6234, 134, ---, 234]
然后从51的下个值往右扫，发现452>100，那么把452填入上面挖的坑
[51, 23, ---, 234, 56223, 6234, 134, 452, 234]
然后从452往左扫描，发现没有小于100的。那么100 就只能去填坑了。自此我们做了一个循环。
[51, 23, 100 234, 56223, 6234, 134, 452, 234]
那么下一个循环我们怎么开始呢？因为100的右边肯定是大于它的，100的左边肯定是小于它的。PS.这不是废话吗？上面的快排就是这样要求的。
我们就从51，到100 这三个元素之间继续排序。
[51,23,100]
[--,23,100]
[23,--,100]
[23,50,100]
最左边的完成了，那么我们来看看最右边的
[234,56223,6234, 134, 452, 234]
.... 各位看官自己实现下看看？
好了直接上代码
<?php
function quickSort(&$input, $low, $high)
{
if ($high <= $low) return;
$i = $low;
$j = $high;
$key = $input[$low];
while ($i < $j) {
while ($i < $j && $input[$j] >= $key) {
$j--;
}
if ($i < $j) {
$input[$i] = $input[$j];
$i++;
}
while ($i < $j && $input[$i] < $key) {
$i++;
}
if ($i < $j) {
$input[$j] = $input[$i];
$j--;
}
// printf("find i(%d),j(%d)\n", $i, $j);
}
$input[$i] = $key;
quickSort($input, $low, $i - 1);
quickSort($input, $i + 1, $high);
// return $input;
}
为了节省递归参数赋值，我们传了引用进去，更加节省内存空间。那么具体效果如何呢，我们来看看跟内置函数sort的对比结果。
排序个数：100000
内置排序耗时：27.215004 ms
手写排序耗时：104.742050 ms
结果抽查 1
排序个数：200000
内置排序耗时：61.784983 ms
手写排序耗时：241.871119 ms
结果抽查 1
排序个数：300000
内置排序耗时：87.085009 ms
手写排序耗时：448.505878 ms
结果抽查 1
排序个数：400000
内置排序耗时：120.175838 ms
手写排序耗时：618.201971 ms
结果抽查 1
排序个数：500000
内置排序耗时：149.783850 ms
手写排序耗时：796.765804 ms
结果抽查 1
排序个数：600000
内置排序耗时：182.029963 ms
手写排序耗时：1063.417196 ms
结果抽查 1
排序个数：700000
内置排序耗时：209.767103 ms
手写排序耗时：1333.762884 ms
结果抽查 1
排序个数：800000
内置排序耗时：241.870165 ms
手写排序耗时：1633.098841 ms
结果抽查 1
排序个数：900000
内置排序耗时：272.398949 ms
手写排序耗时：1975.782871 ms
结果抽查 1
排序个数：1000000
内置排序耗时：299.492121 ms
手写排序耗时：2303.519964 ms
结果抽查 1
可以看出虽然我们采用了传引用的方法，在大量的数据排序的时候，自己写的还是没有内置的厉害。基本上内置的算法只需要自己写的1/5的时间。
那么是否别的语言也是这样的呢？我们来看看golang吧。
排序个数： 100000
内置排序耗时： 16.072056ms
手写排序耗时： 6.95578ms
结果抽查: true
排序个数： 200000
内置排序耗时： 31.831613ms
手写排序耗时： 14.822814ms
结果抽查: true
排序个数： 300000
内置排序耗时： 46.872946ms
手写排序耗时： 24.190585ms
结果抽查: true
排序个数： 400000
内置排序耗时： 66.008501ms
手写排序耗时： 33.844555ms
结果抽查: true
排序个数： 500000
内置排序耗时： 77.824994ms
手写排序耗时： 43.05986ms
结果抽查: true
排序个数： 600000
内置排序耗时： 106.42095ms
手写排序耗时： 53.728681ms
结果抽查: true
排序个数： 700000
内置排序耗时： 117.377987ms
手写排序耗时： 65.855924ms
结果抽查: true
排序个数： 800000
内置排序耗时： 125.352682ms
手写排序耗时： 80.507389ms
结果抽查: true
排序个数： 900000
内置排序耗时： 140.563745ms
手写排序耗时： 92.550294ms
结果抽查: true
排序个数： 1000000
内置排序耗时： 162.15016ms
手写排序耗时： 100.330999ms
结果抽查: true
可以看到golang手写的居然比内置的快。100万个int排序，golang内置需要162ms，手写的居然只要100ms，php内置需要299ms，而手写居然需要2300多ms。
看来php的执行效率确实低，不过惊讶的是php内置函数排序居然只比golang慢一倍。
电脑配置
CPU：2.8 GHz 双核Intel Core i5
MEM：8 GB 1600 MHz DDR3
PHP version：7.4.2
Golang version ：go1.13.7
最后贴上golang代码
package main
import (
"fmt"
"math/rand"
"sort"
"time"
)
func quickSortCustom(nums *[]int, start int, end int) {
// 起点和终点重合的时候，退出
if start >= end {
return
}
i, j := start, end
//左节点的坑挖出来，备用
mid := (*nums)[start]
for {
// 左节点位移到跟右节点重合时退出for循环
if i >= j {
break
}
// 右节点开始向左查找，直到比基准值小
for {
if j > i && (*nums)[j] >= mid {
j--
} else {
break
}
}
// 把右节点的坑，填入左节点。现在右节点j空出来了
if i < j {
(*nums)[i] = (*nums)[j]
i++
}
// 左节点开始向右寻找，直到找到比基准值大的
for {
if j > i && (*nums)[i] < mid {
i++
} else {
break
}
}
//把左节点的值填入右节点的坑，（上面的右节点j是空的没有变过）。此时左节点i空出来了
if i < j {
(*nums)[j] = (*nums)[i]
j--
}
}
// 把最开始挖出来的坑放到新坑里面
(*nums)[i] = mid
quickSortCustom(nums, start, i-1)
quickSortCustom(nums, i+1, end)
}
type IntSlice []int
func (s IntSlice) Less(i, j int) bool { return s[i] < s[j] }
func (s IntSlice) Len() int { return len(s) }
func (s IntSlice) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
func main() {
startTime := time.Now()
for i := 100000; i <= 1000000; i += 100000 {
numsIn := make(IntSlice, 0)
numsMy := make([]int, 0)
for n := 0; n < i; n++ {
//rand.Seed(int64(n))
x := rand.Intn(10000)
numsIn = append(numsIn, x)
numsMy = append(numsMy, x)
}
l := len(numsMy)
//fmt.Println("原始:", numsMy, "排序个数：", l)
fmt.Println("排序个数：", l)
// ---------------- 内置排序 开始----------------
startTime = time.Now()
sort.Ints(numsIn)
cost := time.Since(startTime)
fmt.Println("内置排序耗时：", cost)
// ---------------- 内置排序 结束----------------
// ---------------- 手写排序 开始----------------
startTime = time.Now()
quickSortCustom(&numsMy, 0, l-1)
cost = time.Since(startTime)
fmt.Println("手写排序耗时：", cost)
// ---------------- 手写排序 结束----------------
fmt.Println("结果抽查:", numsMy[l/2] == numsIn[l/2])
//fmt.Println("内置:", numsIn)
//fmt.Println("手写:", numsMy)
fmt.Println(" ")
}
//nums := []int{8081, 7887, 1847, 4059, 2081, 1318, 4425, 2540, 456, 3300}
//fmt.Println("原始的数据:", nums)
//quickSortCustom(&nums, 0, len(nums)-1)
//fmt.Println("自己排序后:", nums)
//
//nums2 := IntSlice{8081, 7887, 1847, 4059, 2081, 1318, 4425, 2540, 456, 3300}
////fmt.Println("排序前:",nums2)
//sort.Stable(nums2)
//fmt.Println("内置排序后:", nums2)
}