快速排序

排序

说明

按基准值分区并递归处理；平均 O(n log n)，最坏 O(n²)。

分析

选择一个基准值，用双指针把较小值移到左侧、较大值移到右侧，再分别递归。分区均衡时性能很好；若基准长期偏向一侧，递归深度和时间会恶化。

图解推演

正文 [3,1,2] 选中间值 1 为基准，左右扫描后交换 3 与 1，得到 [1,3,2]，再递归后缀并得到 [1,2,3]。相等值交换后也要推进两个游标，否则重复元素可能使循环停滞。分区完成只保证两侧符合基准约束，并不意味着每一侧已经有序。

查看图表代码

适用前提与边界

工程实现通常加入随机化或深度限制。

示例输入与调用

a := []int{3, 1, 2}
	QuickSort(a)
	fmt.Println(a)

运行输出

[1 2 3]

完整 Go 示例

package main

import "fmt"

func QuickSort(a []int) {
	if len(a) < 2 {
		return
	}
	pivot := a[len(a)/2]
	i, j := 0, len(a)-1
	for i <= j {
		for a[i] < pivot {
			i++
		}
		for a[j] > pivot {
			j--
		}
		if i <= j {
			a[i], a[j] = a[j], a[i]
			i++
			j--
		}
	}
	if j >= 0 {
		QuickSort(a[:j+1])
	}
	if i < len(a) {
		QuickSort(a[i:])
	}
}

func main() {
	a := []int{3, 1, 2}
	QuickSort(a)
	fmt.Println(a)
}