快速排序 #
步骤如下：
- 先从数列中取出一个数作为基准数。一般取第一个数。
- 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
- 再对左右区间重复第二步，直到各区间只有一个数。
举一个例子：5 9 1 6 8 14 6 49 25 4 6 3。
一般取第一个数 5 作为基准，从它左边和最后一个数使用[]进行标志，
如果左边的数比基准数大，那么该数要往右边扔，也就是两个[]数交换，这样大于它的数就在右边了，然后右边[]数左移，否则左边[]数右移。
5 [9] 1 6 8 14 6 49 25 4 6 [3] 因为 9 > 5，两个[]交换位置后，右边[]左移
5 [3] 1 6 8 14 6 49 25 4 [6] 9 因为 3 !> 5，两个[]不需要交换，左边[]右移
5 3 [1] 6 8 14 6 49 25 4 [6] 9 因为 1 !> 5，两个[]不需要交换，左边[]右移
5 3 1 [6] 8 14 6 49 25 4 [6] 9 因为 6 > 5，两个[]交换位置后，右边[]左移
5 3 1 [6] 8 14 6 49 25 [4] 6 9 因为 6 > 5，两个[]交换位置后，右边[]左移
5 3 1 [4] 8 14 6 49 [25] 6 6 9 因为 4 !> 5，两个[]不需要交换，左边[]右移
5 3 1 4 [8] 14 6 49 [25] 6 6 9 因为 8 > 5，两个[]交换位置后，右边[]左移
5 3 1 4 [25] 14 6 [49] 8 6 6 9 因为 25 > 5，两个[]交换位置后，右边[]左移
5 3 1 4 [49] 14 [6] 25 8 6 6 9 因为 49 > 5，两个[]交换位置后，右边[]左移
5 3 1 4 [6] [14] 49 25 8 6 6 9 因为 6 > 5，两个[]交换位置后，右边[]左移
5 3 1 4 [14] 6 49 25 8 6 6 9 两个[]已经汇总，因为 14 > 5，所以 5 和[]之前的数 4 交换位置
第一轮切分结果：4 3 1 5 14 6 49 25 8 6 6 9
现在第一轮快速排序已经将数列分成两个部分：
4 3 1 和 14 6 49 25 8 6 6 9
左边的数列都小于 5，右边的数列都大于 5。
使用递归分别对两个数列进行快速排序。
package main
import "fmt"
type BinaryTreeNode struct {
Value int
Left, Right *BinaryTreeNode
}
func main() {
nums := []int{4, 7, 2, 9, 3, 1}
quickSort(nums, 0, len(nums)-1)
fmt.Println(nums)
}
func quickSort(nums []int, r, l int) {
if r < l {
loc := quickSortHelper(nums, r, l)
quickSort(nums, r, loc-1)
quickSort(nums, loc+1, l)
}
}
func quickSortHelper(nums []int, r, l int) int {
i := r + 1
j := l
for i < j {
if nums[i] > nums[r] {
nums[i], nums[j] = nums[j], nums[i]
j--
} else {
i++
}
}
if nums[r] <= nums[i] {
i--
}
nums[r], nums[i] = nums[i], nums[r]
return i
}