算法描述
算法描述：是对插入算法的一种优化，利用对问题的二分化，实现递归完成快速排序 ，在所有算法中二分化是最常用的方式，将问题尽量的分成两种情况加以分析， 最终以形成类似树的方式加以利用，因为在比较模型中的算法中，最快的排序时间 负载度为 O(nlgn)。
算法步骤
- 将数据根据一个值按照大小分成左右两边，左边小于此值，右边大于
- 将两边数据进行递归调用步骤1
- 将所有数据合并
代码
package main
import "fmt"
func QuickSort1(arr []int) []int {
if len(arr) <= 1 {
return arr
}
splitData := arr[0] //第一个数据
low := make([]int, 0, 0) //比第一个数小的数据
high := make([]int, 0, 0) //比第一个数大的数据
mid := make([]int, 0, 0) //与第一个数一样大的数据
mid = append(mid, splitData) //把第一个数加入到mid切片
for i := 1; i < len(arr); i++ {
if arr[i] < splitData {
low = append(low, arr[i])
} else if arr[i] > splitData {
high = append(high, arr[i])
} else {
mid = append(mid, arr[i])
}
}
low, high = QuickSort1(low), QuickSort1(high)
myArr := append(append(low, mid...), high...)
return myArr
}
func QuickSort2(left int, right int, arr []int) {
i, j := left, right
mid := arr[(left + right) / 2] //将当前序列在中间位的数定义为分隔数
for i <= j {
for arr[i] < mid { //扫描左半部分比分隔数大的数
i++
}
for arr[j] > mid { //扫描右半部分比分隔数小的数
j--
}
if i <= j { //交换上述找到的两个数
arr[i], arr[j] = arr[j], arr[i]
i++
j--
}
}
if left < j {
QuickSort2(left, j, arr)
}
if i < right {
QuickSort2(i, right, arr)
}
}
func main() {
arr := []int{1, 9, 10, 30, 2, 5, 45, 8, 63, 234, 12}
fmt.Println(QuickSort1(arr))
//QuickSort2(0, len(arr) - 1, arr)
//fmt.Println(arr)
}
输出结果：
[1 2 5 8 9 10 12 30 45 63 234]
目测QuickSort2会更节约内存，因为每调用一次QuickSort1都会为3个切片分配底层数组，如果数据非常大，可能会非常耗费内存。