快速排序

参考文章：

• https://sort.hust.cc/6.quicksort
• https://www.bilibili.com/video/BV1at411T75o
• https://www.bilibili.com/video/BV1mE411M7SH
• https://selfboot.cn/2016/09/01/lost_partition/

怎么说呢，php版本的快排是比较易于理解，按照这个思路写了一个golang版本的

算法步骤
1、先从list取出一个元素，作为基准数 pivot
2、将list中的元素与 基准数比较 遍历一遍，然后将比基准数小的放左边，比基准数大的放右边，和基准数相同的放左放后都行。如此操作一遍后，基准数就会处于 list数据 中间位置，

PHP版本

<?php

var_dump(quickSort([5, 9, 1]));
var_dump(quickSort([5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3]));

function quickSort(array $arr): array {
    if (count($arr) <= 1) {
        return $arr;
    }
    $mid = $arr[0];

    $leftArr = [];
    $rightArr = [];

    for ($i = 1; $i < count($arr); $i++) {
        if ($mid >= $arr[$i]) {
            $leftArr[] = $arr[$i];
        } else {
            $rightArr[] = $arr[$i];
        }
    }

    $leftArr = quickSort($leftArr);
    $leftArr[] = $mid;
    $rightArr = quickSort($rightArr);

    return array_merge($leftArr, $rightArr);
}

package main

import "fmt"

// 快速排序: 快速排序通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

// 步骤如下：
// 先从数列中取出一个数作为基准数。一般取第一个数。
// 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
// 再对左右区间重复第二步，直到各区间只有一个数。

func main() {
	list := []int{5}
	fmt.Println(QuickSort3(list))

	list1 := []int{5, 9}
	fmt.Println(QuickSort3(list1))

	list2 := []int{5, 9, 1}
	fmt.Println(QuickSort3(list2))

	list3 := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
	fmt.Println(QuickSort3(list3))
}

//QuickSort3 参考php版本的快排写的一个golang版本
func QuickSort3(slice []int) []int {
	if cap(append(slice)) <= 1 {
		return slice
	}
	pivot := slice[0]

	var leftSlice []int
	var rightSlice []int

	for i := 1; i < len(slice); i++ {
		if slice[i] <= pivot {
			leftSlice = append(leftSlice, slice[i])
		} else {
			rightSlice = append(rightSlice, slice[i])
		}
	}

	leftSlice = QuickSort3(leftSlice)
	leftSlice = append(leftSlice, pivot)
	rightSlice = QuickSort3(rightSlice)

	return append(leftSlice, rightSlice...)
}