algorithm/quick_sort.go at master · pihou/algorithm · GitHub

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
50
51
52
53
54
55
56
57
58
59
60
61
package main

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

func quick_sort(a []int) {
	if a == nil || len(a) <= 1 {
		return
	}
	// h <head> t <tail> l <last>
	l := len(a) - 1
	pivot := a[l]
	h, t := 0, l
	for h < t {
		for h < t && a[h] <= pivot {
			h++
		}
		for h < t && a[t] >= pivot {
			t--
		}
		a[h], a[t] = a[t], a[h]
	}
	a[h], a[l] = a[l], a[h]
	quick_sort(a[:h])
	quick_sort(a[h+1:])
}

func main() {
	t := [][]int{
		{1, 2, 3},
		{1, 1, 1},
		{3, 2, 1},
		{1},
		{1, 100},
	}
	for _, d := range t {
		quick_sort(d)
		fmt.Println(d)
	}
	for i := 0; i < 12; i++ {
		d := []int{}
		for j := 0; j < 120; j++ {
			d = append(d, rand.Intn(100))
		}
		t := make([]int, len(d))
		copy(t, d)
		quick_sort(d)
		sort.Ints(t)
		for in, data := range t {
			if data != d[in] {
				fmt.Println("Not Right:")
				fmt.Println(d)
				fmt.Println(t)
				break
			}
		}
	}
}