快速排序就像整理书架上的书。
假设你有一堆书，乱七八糟放在桌子上，你要按厚度从薄到厚排序。

它不傻乎乎地一本一本插到正确位置（那是插入排序的风格），而是用“**分而治之”**的策略：
随便挑一本书（叫“基准”或 pivot）
把剩下的书分成两堆：
比它薄的放左边
比它厚的放右边
现在左边、右边的书还没排好，但它们彼此之间已经不打扰了（薄的全在左，厚的全在右）。
对左边这堆再做同样的事，对右边那堆也一样。
直到每一堆只剩一本书（天然有序），所有堆合在一起就是排序好的结果。

优点

• 平均速度很快，时间复杂度 O(n log n)
• 不需要额外很大空间（可以原地排序）
• 分治策略天然适合递归实现

缺点

• 最坏情况会退化到 O(n²)（比如数组本来就是有序的，而且你每次都选第一个元素做基准）
• 递归太深可能会爆栈（特别是超长数组）

最精炼的口诀

选基准 → 分左右 → 递归排 → 合并好

package algorithm

import "golang.org/x/exp/constraints"

// QuickSort 使用泛型实现快速排序
func QuickSort[T constraints.Ordered](arr []T, left, right int) {
	if left >= right {
		return
	}

	// 选取基准（这里用最左边的元素）
	pivot := arr[left]
	i, j := left, right

	for i < j {
		// 从右往左找到第一个小于 pivot 的
		for i < j && arr[j] >= pivot {
			j--
		}
		// 从左往右找到第一个大于 pivot 的
		for i < j && arr[i] <= pivot {
			i++
		}
		// 你选的 pivot 是 arr[left]，而且在整个分区过程中 pivot 暂时还放在数组最左边。
		//	这就决定了分区的第一步必须先从右边往左找小于 pivot 的元素，这样能保证最终 i 停在的位置是安全的。

		// 交换
		if i < j {
			arr[i], arr[j] = arr[j], arr[i]
		}
	}

	// 将 pivot 放到正确位置
	arr[left], arr[i] = arr[i], arr[left]

	// 递归排序左右两边	递归需要显式说明泛型
	QuickSort[T](arr, left, i-1)
	QuickSort[T](arr, i+1, right)
}