Quick Sort

快速排序（quick sort） 是一种基于 分治 的排序算法，是当前最常用的排序算法。

快速排序的核心操作是“哨兵划分”，其目标是：选择数组中的某个元素作为“基准数”，将所有小于基准数的元素移到其左侧，而大于基准数的元素移到其右侧。

哨兵划分完成后，原数组被划分成三部分：左子数组、基准数、右子数组，且满足“左子数组任意元素 <= 基准数 <= 右子数组任意元素”。因此，我们接下来只需对这两个子数组递归快速排序即可。^[1]

代码

func QuickSort(arr []int) []int {
	if len(arr) > 1 {
		pivot := partition(arr)
		QuickSort(arr[0:pivot])
		QuickSort(arr[pivot+1:])
	}
	return arr
}

func partition(arr []int) int {
	lo, base := 0, len(arr)-1
	for i := 0; i < base; i++ {
		if arr[i] < arr[base] {
			arr[lo], arr[i] = arr[i], arr[lo]
			lo++
		}
	}
	arr[lo], arr[base] = arr[base], arr[lo]
	return lo
}