golang实现快排的不同思路

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

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

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)
}