算法

背景

快速排序是编程中最常用的一种排序，时间级别为O(nlogn)级别，空间级别为常量级T(1)。快速算法是一种通过基准值分治排序的算法，基准值左边值的都小于基准值，基准值右边的值都大于等于基准值。递归左右子集，按基准值排序，所有子集排序后的结果即为整个数组的排序结果。

代码

快速排序算法的基准值应随机选取，否则对于一些比较特殊的情况会一直以很慢的速度执行。

package main

import (
	"math/rand"
)

// 快速排序
// 实际使用前应先调用一次随机种子rand.Seed(time.Now().UnixNano())
func quickSort(a []int) []int {
        // 当数组元素只有一个时直接返回原数组
	if len(a) < 2 {
		return a
	}
        // 获取左右侧边界索引
	left, right := 0, len(a)-1

	// 随机选取基准值
	pivotIndex := rand.Int() % len(a)

	// 将基准值移到最右侧，目的是方便数组排序
	a[pivotIndex], a[right] = a[right], a[pivotIndex]

	// 如果数组当前元素小于基准值，则将元素移到左边界
	for i := range a {
		if a[i] < a[right] {
			a[i], a[left] = a[left], a[i]
			left++
		}
	}

	// 将基准值与基准值右侧最靠近基准值的元素交换
        // 因方便排序，前边将元素交换到右侧，现在换回到基准值的原本位置
        // 该位置刚好对应上当前左侧边界位置
	a[left], a[right] = a[right], a[left]

	// 对分治后的左右数组重复执行上述操作
	quickSort(a[:left])
	quickSort(a[left+1:])

	return a
}