一直不喜欢快速排序的那种常见实现方法,因为总有一些奇奇怪怪的边界值,什么时候用等于,什么时候该用大于等于一直弄不清楚。
这里找到一种很容易理解的实现方法,反正我个人很喜欢。
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) }
|