使用 Go 实现快速排序

 1 package main
 2 import (
 3    "fmt"
 4    "math/rand"
 5    "sort"
 6    "time"
 7    "github.com/psilva261/timsort"
 8 )
 9 func partition(a []int, lo, hi int) int {
10    pivot := a[hi]
11    i := lo - 1
12    for j := lo; j < hi; j++ {
13        if a[j] < pivot {
14            i++
15            a[j], a[i] = a[i], a[j]
16        }
17    }
18    a[i+1], a[hi] = a[hi], a[i+1]
19    return i + 1
20 }
21 func quickSort(a []int, lo, hi int) {
22    if lo >= hi {
23        return
24    }
25    p := partition(a, lo, hi)
26    quickSort(a, lo, p-1)
27    quickSort(a, p+1, hi)
28}
29 func quickSort_go(a []int, lo, hi int, done chan struct{}, depth int) {
30    if lo >= hi {
31        done <- struct{}{}
32        return
33    }
34    depth--
35    p := partition(a, lo, hi)
36    if depth > 0 {
37        childDone := make(chan struct{}, 2)
38        go quickSort_go(a, lo, p-1, childDone, depth)
39        go quickSort_go(a, p+1, hi, childDone, depth)
40        <-childDone
41        <-childDone
42    } else {
43        quickSort(a, lo, p-1)
44        quickSort(a, p+1, hi)
45    }
46    done <- struct{}{}
47 }
48 func main() {
49    rand.Seed(time.Now().UnixNano())
50    testData1, testData2, testData3, testData4 := make([]int, 0, 100000000), make([]int, 0, 100000000), make([]int, 0, 100000000), make([]int, 0, 100000000)
51    times := 100000000
52    for i := 0; i < times; i++ {
53        val := rand.Intn(20000000)
54        testData1 = append(testData1, val)
55        testData2 = append(testData2, val)
56        testData3 = append(testData3, val)
57        testData4 = append(testData4, val)
58    }
59    start := time.Now()
60    quickSort(testData1, 0, len(testData1)-1)
61    fmt.Println("single goroutine: ", time.Now().Sub(start))
62    if !sort.IntsAreSorted(testData1) {
63        fmt.Println("wrong quick_sort implementation")
64    }
65    done := make(chan struct{})
66    start = time.Now()
67    go quickSort_go(testData2, 0, len(testData2)-1, done, 5)
68    <-done
69    fmt.Println("multiple goroutine: ", time.Now().Sub(start))
70    if !sort.IntsAreSorted(testData2) {
71        fmt.Println("wrong quickSort_go implementation")
72    }
73    start = time.Now()
74    sort.Ints(testData3)
75    fmt.Println("std lib: ", time.Now().Sub(start))
76    if !sort.IntsAreSorted(testData3) {
77        fmt.Println("wrong std lib implementation")
78    }
79    start = time.Now()
80    timsort.Ints(testData4, func(a, b int) bool { return a <= b })
81    fmt.Println("timsort: ", time.Now().Sub(start))
82    if !sort.IntsAreSorted(testData4) {
83        fmt.Println("wrong timsort implementation")
84    }
85}