You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
|
|
|
|
package goConcurrency
|
|
|
|
|
|
|
|
|
|
import (
|
|
|
|
|
"math/rand"
|
|
|
|
|
"sync"
|
|
|
|
|
"time"
|
|
|
|
|
)
|
|
|
|
|
|
|
|
|
|
// QuickSortConcurrency 快速排序调用函数
|
|
|
|
|
func QuickSortConcurrency(arr []int) []int {
|
|
|
|
|
// 一:校验arr是否满足排序需要,至少要有2个元素
|
|
|
|
|
if arr == nil || len(arr) < 2 {
|
|
|
|
|
return arr
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// 四:同步的控制
|
|
|
|
|
wg := &sync.WaitGroup{}
|
|
|
|
|
// 二:执行排序
|
|
|
|
|
// 初始排序整体[0, len(arr)-1]
|
|
|
|
|
wg.Add(1)
|
|
|
|
|
go quickSortConcurrency(arr, 0, len(arr)-1, wg)
|
|
|
|
|
wg.Wait()
|
|
|
|
|
|
|
|
|
|
// 三:返回结果
|
|
|
|
|
return arr
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// 实现递归快排的核心函数
|
|
|
|
|
// 接收arr,和排序区间的索引位置[l, r]
|
|
|
|
|
func quickSortConcurrency(arr []int, l, r int, wg *sync.WaitGroup) {
|
|
|
|
|
// 一:-1wg的计数器
|
|
|
|
|
defer wg.Done()
|
|
|
|
|
|
|
|
|
|
// 二:判定是否需要排序, l < r
|
|
|
|
|
if l < r {
|
|
|
|
|
// 三:大小分区元素,并获取参考元素索引
|
|
|
|
|
mid := partition(arr, l, r)
|
|
|
|
|
|
|
|
|
|
// 四:并发对左部分排序
|
|
|
|
|
wg.Add(1)
|
|
|
|
|
go quickSortConcurrency(arr, l, mid-1, wg)
|
|
|
|
|
|
|
|
|
|
// 五:并发的对右部分排序
|
|
|
|
|
wg.Add(1)
|
|
|
|
|
go quickSortConcurrency(arr, mid+1, r, wg)
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// 大小分区,返回参考元素索引
|
|
|
|
|
func partition(arr []int, l, r int) int {
|
|
|
|
|
p := l - 1
|
|
|
|
|
for i := l; i <= r; i++ {
|
|
|
|
|
if arr[i] <= arr[r] {
|
|
|
|
|
p++
|
|
|
|
|
swap(arr, p, i)
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
return p
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// 交换arr中i和j元素
|
|
|
|
|
func swap(arr []int, i, j int) {
|
|
|
|
|
t := arr[i]
|
|
|
|
|
arr[i] = arr[j]
|
|
|
|
|
arr[j] = t
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// 生成大的随机数组
|
|
|
|
|
func GenerateRandArr(l int) []int {
|
|
|
|
|
// 生产大量的随机数
|
|
|
|
|
arr := make([]int, l)
|
|
|
|
|
rand.Seed(time.Now().UnixMilli())
|
|
|
|
|
for i := 0; i < l; i++ {
|
|
|
|
|
arr[i] = int(rand.Int31n(int32(l * 5)))
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
return arr
|
|
|
|
|
}
|