曾经有一个人让我写下快排算法，我给他写出来了，然后就被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)
}