一直不喜欢快速排序的那种常见实现方法,因为总有一些奇奇怪怪的边界值,什么时候用等于,什么时候该用大于等于一直弄不清楚。

这里找到一种很容易理解的实现方法,反正我个人很喜欢。

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
package main

import "fmt"

func partition(arr []int, begin, end int) int {
i := begin + 1
j := end
for i < j {
if arr[i] > arr[begin] {
arr[i], arr[j] = arr[j], arr[i]
j--
} else {
i++
}
}

if arr[begin] <= arr[j] {//这里需要加上等于,为了保证元素全部相等时仍然可以正常运行
i--
}

arr[begin], arr[i] = arr[i], arr[begin] //最后交换
return i
}

func quickSort(arr []int, begin, end int) {
if begin < end {
pos := partition(arr, begin, end)
quickSort(arr, begin, pos - 1)
quickSort(arr, pos + 1, end)
}
}

func main() {
s := []int{1, 1, 4, 5, 1, 4, 1, 9, 1, 9, 8, 1, 0}
quickSort(s, 0, len(s) - 1)
fmt.Println(s)
}