快速排序算法的核心是在一个数组中，将第一个元素放置在中间位置使这个数组变为左边比这个元素都小，右边比这个组都大的一个数组。
代码实现这个过程如下
// 找出arr[l...r]的分界点j
// 使其分为arr[l,j] arr[j+1,r]两部分
func partition(arr []int, l, r) int {
// j为当前找到的分界点
// v为做为分界点的值
j, v := l, arr[l]
// i为当前正在考察的元素
for i := l+1; i <= r; i++ {
if arr[i] < v {
arr[j+1], arr[i] = arr[i], arr[j+1]
j++
}
}
a[j], a[l] = a[l], a[j]
return j
}
然后快速排序就是递归调用这个方法，将整个数组分为两部分，继续再分为四部分，直到每个数组只有一个元素就完成了排序
代码如下：
// QuickSort 快速排序
func QuickSort(arr []int) {
quickSort(arr, 0, len(arr)-1)
}
// 对arr的[l,r]快速排序
func quickSort(arr []int, l int, r int) {
if l >= r {
return
}
p := partition(arr, l, r)
quickSort(arr, l, p-1)
quickSort(arr, p+1, r)
}
// 找出arr的[l,r]的标识点
func partition(arr []int, l int, r int) int {
// arr[l+1:j] < v arr[j+1:i) > v
// i为正在考察的元素
v, j := arr[l], l
for i := l + 1; i <= r; i++ {
if arr[i] < v {
arr[j+1], arr[i] = arr[i], arr[j+1]
j++
}
}
arr[j], arr[l] = arr[l], arr[j]
return j
}
