go - 并发快速排序

Question

所以我在 go 中实现了一个快速排序算法。我使用 go test 对其进行了测试，效果非常好。现在我想让它并发并检查计算时间的差异。算法如下所示:

package mysort

import (
    "math/rand"
)

// ConcurrentPartition - ConcurrentQuicksort function for partitioning the array (randomized choice of a pivot)
func ConcurrentPartition(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
}

// ConcurrentQuicksort - a concurrent version of a quicksort algorithm
func ConcurrentQuicksort(A []int, p int, r int) {
    if p < r {
        q := ConcurrentPartition(A, p, r)
        ConcurrentQuicksort(A, p, q-1)
        ConcurrentQuicksort(A, q+1, r)
    }
}

每个 ConcurrentQuicksort 默认情况下都是独立的，因为它建立在 divide and conquer 哲学之上。所以我唯一做的就是在每次递归调用之前添加 go 关键字，如下所示:

go ConcurrentQuicksort(A, p, q-1)
go ConcurrentQuicksort(A, q+1, r)

我没有工作。正如我所见，它只是采用了一个数组，甚至没有一次调用递归快速排序。所以我添加了 time import 和这一行:

time.Sleep(time.Second * 2)(在 if 之后)

它奏效了。所以我猜它需要时间来完成所有操作。我现在怎样才能不等待呢？我应该使用 channel ，还是以不同的方式调用函数？

@Edit 添加了这个:

func ConcurrentQuicksort(A []int, p int, r int, wg *sync.WaitGroup) {
    if p < r {
        q := ConcurrentPartition(A, p, r)
        wg.Add(2)
        go ConcurrentQuicksort(A, p, q-1, wg)
        go ConcurrentQuicksort(A, q+1, r, wg)
    }
}

Answer 1

你可以在这里使用sync包。创建 WaitGroup在您所有的 go 例程实际完成之前，实际上不会进一步深入线程。它有非常简单的界面。这是使用示例。

func main() {
    var wg sync.WaitGroup

    for i := 0; i < 1000; i++ {
        wg.Add(1)
        go func(index int) {
            defer wg.Done()
            fmt.Println("I'm done and my index is", index)
        }(i)
    }

    wg.Wait()

    fmt.Println("This message is actually printed after all goroutines are done")
}