# go 协程实现快排 V2

使用了 sync.WaitGroup 对 p 的左右两边进行有序的排序

测试出来使用协程进行排序的效果差于单线程。

现在重新优化了几个版本。

每次递归之后，到最后对于只有几个元素的情况下，再开辟协程进行快排，会大量的创建资源和调用 Goroutine，资源消耗主要不是在排序，而是在创建 Goroutine。所以只有几个元素的情况，会直接使用单线程进行排序。
使用 sync.WaitGroup 的进行阻塞，在这种情况下不如使用 chan 进行阻塞
测试机器性能有问题，之前在 4 核的机器上进行测试，goroutine 开启数量只有两个，后续换到本地电脑，开启了 20 个 goroutine ，和单线程模式进行比较，效率明显提升了不少。

# 代码

	package quicksort

	type v1 struct{}

	func QuickSortV1(list []int) []int {
	if len(list) <= 1 {
	return list
	}

	v1{}.quicksort(list, 0, len(list)-1)
	return list
	}

	func (v v1) quicksort(list []int, low, high int) {
	if low >= high {
	return
	}

	p := v.partion(list, low, high)

	v.quicksort(list, low, p-1)
	v.quicksort(list, p+1, high)
	}

	func (v1) partion(list []int, low, high int) int {
	p := list[low]

	// 移动左右指针
	for low < high {

	// 从高的地方，找到小于 p 的值，迁移
	for low < high && p <= list[high] {
	high--
	}
	list[low] = list[high]
	// fmt.Println(low, high, list)

	// 从低的地方，找到大于 p 的值，迁移
	for low < high && p >= list[low] {
	low++
	}
	list[high] = list[low]
	// fmt.Println(low, high, list)
	}

	// 插入 p
	list[low] = p
	// fmt.Println(low, high, list)
	// fmt.Println("====")
	return low
	}

	package quicksort

	import "sync"

	type V2 struct {
	minLen int // 小于此值不进行协程操作
	}

	// 通过 WaitGroup 实现有序
	func QuickSortV2(list []int, minLen int) []int {
	if len(list) <= 1 {
	return list
	}
	v := V2{minLen}
	v.quicksort(list)
	return list
	}

	func (v V2) quicksort(list []int) {

	low := 0
	high := len(list) - 1

	if low >= high {
	return
	}

	p := v.partion(list)

	if len(list) < v.minLen {
	v.quicksort(list[:p])
	v.quicksort(list[p+1:])
	return
	}
	wg := sync.WaitGroup{}

	wg.Add(2)
	go func() {
	v.quicksort(list[:p])
	wg.Done()
	}()

	go func() {
	v.quicksort(list[p+1:])
	wg.Done()
	}()

	wg.Wait()
	}

	func (v V2) partion(list []int) int {
	low := 0
	high := len(list) - 1

	p := list[low]

	// 移动左右指针
	for low < high {

	for low < high && p <= list[high] {
	high--
	}
	list[low] = list[high]

	for low < high && p >= list[low] {
	low++
	}
	list[high] = list[low]
	}

	list[low] = p

	return low
	}

	package quicksort

	type V4 struct {
	minLen int // 小于此值不进行协程操作
	}

	// 通过 channel 实现有序
	func QuickSortV4(list []int, minLen int) []int {
	if len(list) <= 1 {
	return list
	}
	v := V4{minLen}
	v.quicksort(list)
	return list
	}

	func (v V4) quicksort(list []int) {

	low := 0
	high := len(list) - 1

	if low >= high {
	return
	}

	p := v.partion(list)

	if len(list) < v.minLen {
	v.quicksort(list[:p])
	v.quicksort(list[p+1:])
	return
	}

	chanReceive := make(chan bool)
	go func() {
	v.quicksort(list[:p])
	chanReceive <- true
	}()

	go func() {
	v.quicksort(list[p+1:])
	chanReceive <- true
	}()

	<-chanReceive
	<-chanReceive
	}

	func (v V4) partion(list []int) int {
	low := 0
	high := len(list) - 1

	p := list[low]

	// 移动左右指针
	for low < high {

	for low < high && p <= list[high] {
	high--
	}
	list[low] = list[high]

	for low < high && p >= list[low] {
	low++
	}
	list[high] = list[low]
	}

	list[low] = p

	return low
	}

	func TestQuickSortV4_2(t *testing.T) {
	listLen := 1000000

	var startTime, endTime time.Time
	var list []int

	list = rand.Perm(listLen)
	startTime = time.Now()
	list = QuickSortV1(list)
	endTime = time.Now()

	fmt.Println("V1 耗时", endTime.Sub(startTime))
	fmt.Println("V1 是否有序", sort.IntsAreSorted(list))
	time.Sleep(20 * time.Millisecond)

	list = rand.Perm(listLen)
	startTime = time.Now()
	list = QuickSortV2(list, listLen/100)
	endTime = time.Now()
	fmt.Println("V2 耗时", endTime.Sub(startTime))
	fmt.Println("V2 是否有序", sort.IntsAreSorted(list))
	time.Sleep(20 * time.Millisecond)

	list = rand.Perm(listLen)
	startTime = time.Now()
	list = QuickSortV4(list, 0)
	endTime = time.Now()
	fmt.Println("V4 所有分支都走协程", endTime.Sub(startTime))
	fmt.Println("V4 所有分支都走协程", sort.IntsAreSorted(list))
	time.Sleep(20 * time.Millisecond)

	list = rand.Perm(listLen)
	startTime = time.Now()
	list = QuickSortV4(list, listLen/100)
	endTime = time.Now()
	fmt.Println("V4 耗时", endTime.Sub(startTime))
	fmt.Println("V4 是否有序", sort.IntsAreSorted(list))
	time.Sleep(20 * time.Millisecond)
	}

	func BenchmarkQuickSortV1(b *testing.B) {
	minLen := 1000000
	for i := 0; i < b.N; i++ {
	b.StopTimer()
	list := rand.Perm(minLen)
	b.StartTimer()
	list = QuickSortV1(list)
	}
	}

	func BenchmarkQuickSortV2(b *testing.B) {
	minLen := 1000000
	for i := 0; i < b.N; i++ {
	b.StopTimer()
	list := rand.Perm(minLen)
	b.StartTimer()
	list = QuickSortV2(list, 100)
	}
	}

	func BenchmarkQuickSortV4(b *testing.B) {
	minLen := 1000000
	for i := 0; i < b.N; i++ {
	b.StopTimer()
	list := rand.Perm(minLen)
	b.StartTimer()
	list = QuickSortV4(list, 100)
	}
	}

i7-12700 20 线程

N100 4 线程

	$ go test -bench .
	goos: linux
	goarch: amd64
	pkg: twelveeee.top/leetcode/v2/quickSort
	cpu: Intel(R) N100
	BenchmarkQuickSortV1-4 12 96833933 ns/op
	BenchmarkQuickSortV2-4 28 42158544 ns/op
	BenchmarkQuickSortV4-4 27 43368713 ns/op
	PASS
	ok twelveeee.top/leetcode/v2/quickSort 6.194s

i7-12700 20 线程

N100 4 线程

	$ go test -bench .
	goos: linux
	goarch: amd64
	pkg: twelveeee.top/leetcode/v2/quickSort
	cpu: Intel(R) N100
	BenchmarkQuickSortV1-4 150 8074418 ns/op
	BenchmarkQuickSortV2-4 201 5572431 ns/op
	BenchmarkQuickSortV4-4 196 5903751 ns/op
	PASS
	ok twelveeee.top/leetcode/v2/quickSort 7.424s

i7-12700 20 线程

N100 4 线程

	$ go test -bench .
	goos: linux
	goarch: amd64
	pkg: twelveeee.top/leetcode/v2/quickSort
	cpu: Intel(R) N100
	BenchmarkQuickSortV1-4 1761 663315 ns/op
	BenchmarkQuickSortV2-4 2185 569286 ns/op
	BenchmarkQuickSortV4-4 1965 579525 ns/op
	PASS
	ok twelveeee.top/leetcode/v2/quickSort 6.136s

明显看到，在机器负载不高，跑大量数据的时候，启用了协程的速度会大于不启用协程的快排。使用 sync.WaitGroup 还是 chan 进行阻塞影响因素会相对小点