我试图同时实现QuickSort。当我运行它并查看已排序的数组时，在数组开头附近有一部分元素未排序，但数组的大部分是未排序的。
下方代码
package main
import (
"fmt"
"math/rand"
//"runtime"
"sync"
"time"
)
func main() {
slice := generateSlice(1000000)
var wg sync.WaitGroup
start := time.Now()
go Quicksort(slice, 0, len(slice)-1, &wg)
wg.Wait()
end := time.Since(start)
fmt.Printf("Sort Time: %v, sorted: %v \n", end, slice)
}
func Quicksort(A []int, p int, r int, wg *sync.WaitGroup) {
if p < r {
q := Partition(A, p, r)
wg.Add(2)
go Quicksort(A, p, q-1, wg)
go Quicksort(A, q+1, r, wg)
}
}
func Partition(A []int, p int, r int) int {
index := rand.Intn(r-p) + p
pivot := A[index]
A[index] = A[r]
A[r] = pivot
x := A[r]
j := p - 1
i := p
for i < r {
if A[i] <= x {
j++
tmp := A[j]
A[j] = A[i]
A[i] = tmp
}
i++
}
temp := A[j+1]
A[j+1] = A[r]
A[r] = temp
return j + 1
}
func generateSlice(size int) []int {
slice := make([]int, size)
rand.Seed(time.Now().UnixNano())
for i := 0; i < size; i++ {
slice[i] = rand.Intn(999) - rand.Intn(999)
}
return slice
}我似乎找不到问题所在，有什么想法吗？
1条答案
按热度按时间3pvhb19x1#
你的实现有很多问题。Hymns For Disco已经在注解中提到了其中的一些。我建议的另一个改变是不要在所有递归函数调用中使用相同的waitGroup。跟踪计数器的增量和减量可能会非常困难，而且可能会导致死锁。
我对你的代码做了一些修改。我认为它运行得很好。注意，“Partition”和“generateSlice”函数保持不变。