快速排序golang版本

快速排序golang版本

应该怎么理解这个过程，i找到了合适的放置位置，然后此时再把它和现在放在最右侧的元素进行交换，那么，最右侧的元素永远是之前一次趟了元素，之后排好序的元素，那么，假如设想一下，是已经有序了吗？毕竟虽然i的不断右移，需要交换的元素越来越少，从而达到排序的目的。

通常上来说： 数据量比较小时用归并排序速度快，快速排序反而不快； 数据量比较大，同时数据的离散性比较低时，快速排序最快； 数据量比较大，同时数据的离散性比较高时，堆排序最快；

func quickSort(nums []int, l, r int) {
	if l < r {
		m := partition(nums, l, r)
		quickSort(nums, l, m-1)
		quickSort(nums, m+1, r)
	}
}

func partition(nums []int, l, r int) int {
	key := nums[r]
	i := l
	j := l
	for j < r {
		if nums[j] < key {
			nums[i], nums[j] = nums[j], nums[i]
			i++
		}
		j++
		nums[i], nums[r] = nums[r], nums[i]
	}
	return i
}