快速排序和二分查找法总结

使用 Go 实现快速排序


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
package main

import (
"fmt"
"math/rand"
"sort"
"time"
)

func partition(a []int, lo, hi int) int {
pivot := a[hi]
i := lo - 1
for j := lo; j < hi; j++ {
if a[j] < pivot {
i++
a[j], a[i] = a[i], a[j]
}
}
a[i+1], a[hi] = a[hi], a[i+1]
return i + 1
}
func quickSort(a []int, lo, hi int) {
if lo >= hi {
return
}
p := partition(a, lo, hi)
quickSort(a, lo, p-1)
quickSort(a, p+1, hi)
}

func main() {
rand.Seed(time.Now().UnixNano())

testData1 := make([]int, 0, 100000000)

times := 100000000

for i := 0; i < times; i++ {
val := rand.Intn(20000000)
testData1 = append(testData1, val)
}

start := time.Now()
quickSort(testData1, 0, len(testData1)-1)
fmt.Println("single goroutine: ", time.Now().Sub(start))
if !sort.IntsAreSorted(testData1) {
fmt.Println("wrong quick_sort implementation")
}
}