使用golang快速排序

 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

func main() {
	// 测试代码
	arr := []int{9, 8, 7, 6, 5, 1, 2, 3, 4, 0}
	fmt.Println(arr)
	quickSort(arr, 0, len(arr))
	fmt.Println(arr)
}
func quickSortInt(arr []int, a, b int) {
	if b-a <= 1 {
		return
	}
	// 使用随机数优化快速排序
	rand.Seed(time.Now().Unix())
	r := rand.Intn(b-a) + a

	c := b - 1
	arr[c], arr[r] = arr[r], arr[c]

	j := a
	for i := a; i < c; i++ {
		if arr[i] < arr[c] {
			arr[j], arr[i] = arr[i], arr[j]
			j++
		}
	}
	arr[j], arr[c] = arr[c], arr[j]
	quickSortInt(arr, a, c)
	quickSortInt(arr, c+1, b)
}