快速排序

二分法排序

排序流程

快速排序算法通过多次比较和交换来实现排序，其排序流程如下：

• (1)首先设定一个分界值，通过该分界值将数组分成左右两部分。
• (2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。
• (3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
• (4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

算法步骤

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

示例代码

package main

import "fmt"

func main() {
	arr := []int{846, 798, 2, 574, 48, 45, 3, 54, 2, 8, 97, 25, 4, 78, 1, 0, 23, 6, 68, 3, 3, 8, 8, 89, 98, 88, 88, 32}
	fmt.Println(QuickSort(arr))
}
func QuickSort(arr []int) []int {
	if len(arr) <= 1 {
		return arr
	}
    //随机取值
	splitData := arr[0]
    //比随机数小的数据的slice
	low := make([]int, 0, 0)
    //比随机数大的数据的slice
	hight := make([]int, 0, 0)
    //和随机数相同的数据的slice
	mid := make([]int, 0, 0)
    //随机数和自己相同先塞入slice
	mid = append(mid, splitData)
	for i := 1; i < len(arr); i++ {
		if arr[i] < splitData {
			low = append(low, arr[i])
		} 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
}