Go使用goroutine并发的快速排序

发布于 2018-04-19 作者 超级苦工 337次 浏览 版块 分享

经典面试题:快速排序。
一般都使用递归,但golang中利用goroutine的并发可以加快。

func QuickSort(data []int) []int {
    if len(data) <= 1 {
        return data
    }
    var wg sync.WaitGroup
    c := data[0]
    var s1, s2 []int

    for k, v := range data {
        if k == 0 {
            continue
        }
        if c > v {
            s2 = append(s2, v)
        } else {
            s1 = append(s1, v)
        }
    }

    wg.Add(2)
    go func() {
        s1 = QuickSort(s1)
        wg.Done()
    }()
    go func() {
        s2 = QuickSort(s2)
        wg.Done()
    }()
    wg.Wait()

    data = []int{c}
    if len(s1) > 0 {
        data = append(s1, data...)
    }
    if len(s2) > 0 {
        data = append(data, s2...)
    }
    return data
}

func main() {
    data := []int{3, 6, 23, 7, 2, 4, 9, 13}
    fmt.Println(QuickSort(data))
}

收藏
暂无回复