快速排序

算法描述：是对插入算法的一种优化，利用对问题的二分化，实现递归完成快速排序 ，
在所有算法中二分化是最常用的方式，将问题尽量的分成两种情况加以分析，
最终以形成类似树的方式加以利用，因为在比较模型中的算法中，最快的排序时间 负载度为 O(nlgn)

算法步骤：

1. 将数据根据一个值按照大小分成左右两边，左边小于此值，右边大于
2. 将两边数据进行递归调用步骤1
3. 将所有数据合并

package main

import "fmt"

// 算法描述：是对插入算法的一种优化，利用对问题的二分化，实现递归完成快速排序 ，
// 在所有算法中二分化是最常用的方式，将问题尽量的分成两种情况加以分析，
// 最终以形成类似树的方式加以利用，因为在比较模型中的算法中，最快的排序时间 负载度为 O(nlgn)

// 算法步骤
// 1.将数据根据一个值按照大小分成左右两边，左边小于此值，右边大于
// 2.将两边数据进行递归调用步骤1
// 3.将所有数据合并

func QuickSort(arr []int) []int {
	// 如果数组大于或者小于1 直接返回原数组
	if len(arr) <= 1 {
		return arr
	}

	// 第一个数据
	splitdata := arr[0]
	// 比我小的数
	low := make([]int, 0)
	//  比我大的数
	hight := make([]int, 0) 
	// 与我一样大的数
	mid := make([]int, 0)
	// 存放等值
	mid = append(mid, splitdata)

	// 拿到了第一个数据，从1开始
	for i := 1; i < len(arr); i++ {
		//比第一个数据小则存入 low
		if arr[i] < splitdata {
			low = append(low, arr[i])
			//比第一个数据大则存入 hight
		} else if arr[i] > splitdata {
			hight = append(hight, arr[i])
			// 否则相等
		} else {
			mid = append(mid, arr[i])
		}
	}

	// 递归排序
	low, hight = QuickSort(low), QuickSort(hight)

	// 合并数据
	myarr := append(append(low, mid...), hight...)

	return myarr

}

//快读排序算法
func main() {
	arr := []int{1, 9, 10, 30, 2, 5, 45, 8, 63, 234, 12}
	fmt.Println(QuickSort(arr))
}