常见的排序算法

序言

我们在一般情况下都了解一些排序算法，比如冒泡、插入、快排等等。最近算法课用到了链表的归并排序，所以我准备把常用的排序算法重新总结一次。

学习路线如下：

阶段	算法	核心思想	重要程度
1	冒泡排序 Bubble Sort	相邻交换	★★★
1	选择排序 Selection Sort	每轮选择最值	★★★
1	插入排序 Insertion Sort	插入到已有序区间	★★★★★
2	希尔排序 Shell Sort	分组插入、逐步缩小间隔	★★★
3	归并排序 Merge Sort	分治 + 合并	★★★★★
3	快速排序 Quick Sort	分治 + Partition	★★★★★
4	堆排序 Heap Sort	堆 + 选择最大值	★★★★★
5	计数排序 Counting Sort	用值作为下标统计	★★★★
5	桶排序 Bucket Sort	分桶后分别排序	★★★
5	基数排序 Radix Sort	按位排序	★★★★

约定：\(n\) 表示元素个数，时间复杂度描述比较、扫描和搬运等基本操作次数的量级；辅助空间指除输入数组以外额外使用的空间，计入递归栈。\(O\) 表示渐近上界；最佳、平均和最坏情况分别讨论不同输入下的开销。平均情况依赖所采用的输入分布。

稳定性：若关键字相等的若干条记录在排序前后的相对顺序不变，则称该排序是稳定的。本文代码大多只处理 int，无法展示“附带记录的身份”，稳定性是对算法行为的理论结论。

0-数据生成器

首先编写一个数据生成以及验证器，作为学习助手：

package main

import (
	"bufio"
	"fmt"
	"math/rand"
	"os"
	"strconv"
	"strings"
	"time"
)

func main() {
	r := rand.New(rand.NewSource(time.Now().UnixNano()))
	n := r.Intn(50) + 1
	fmt.Println(n)
	for i := 0; i < n; i++ {
		num := r.Intn(513) - 256
		if i > 0 {
			fmt.Print(" ")
		}
		fmt.Print(num)
	}
	fmt.Println()
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	fields := strings.Fields(scanner.Text())
	data := make([]int, len(fields))
	for i, field := range fields {
		num, err := strconv.Atoi(field)
		if err != nil {
			fmt.Println("False")
			return
		}
		data[i] = num
	}
	for i := 1; i < len(data); i++ {
		if data[i] < data[i-1] {
			fmt.Println("False")
			return
		}
	}
	fmt.Println("True")
}

程序行为需要准确理解：

生成长度 \(n \in [1, 50]\) 的随机整数，每个值落在 \([-256, 256]\)；先输出 \(n\)，再输出这 \(n\) 个数。
随后读取你输入的一行，把它按空白切分成整数序列，只检查该序列是否非递减（\(a_i \le a_{i+1}\)）。
它不是完整正确性验证器：不核对元素个数、不核对是否与原数据多重集合一致；空输入时循环直接通过，也可能输出 True。
遇到无法解析为整数的字段会直接输出 False 并结束。

后文的基数排序遇到负数会直接 return，因此练习基数排序时需要自行提供非负数据，才能检验正常排序路径。

1-冒泡排序

冒泡排序的基本思想：反复扫描数组，比较相邻两项，若前面一项大于后面一项则交换，从而让较大的元素像气泡一样逐步“浮”到右侧。

要点：

一趟扫描结束后，当前未就绪区间里的最大值一定能到达该趟的最右端，但并不意味着整表已经有序；需要多趟，直到某一趟没有发生交换。
本实现用 isSorted 做提前终止，但内层边界始终是 \(n-1\)，不会随趟数收缩。因此：
- 最佳情况（输入已有序）：只需一趟扫描且无交换，时间 \(O(n)\)；
- 平均、最坏情况：时间 \(O(n^2)\)；
- 辅助空间 \(O(1)\)（仅交换用的临时变量）；
- 稳定：相等元素不会交换，相对顺序保持不变。

package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&arr[i])
	}
	isSorted := false
	for isSorted == false {
		isSorted = true
		for i := 0; i < n-1; i++ {
			if arr[i] > arr[i+1] {
				isSorted = false
				temp := arr[i]
				arr[i] = arr[i+1]
				arr[i+1] = temp
			}
		}
	}
	for i := 0; i < n; i++ {
		fmt.Printf("%v ", arr[i])
	}
}

2-选择排序

每一轮从未排序区间中选出最小（或最大）元素，放到已排序区间的末尾。

原理与实现对应：

第 \(i\) 轮在 \([i, n)\) 中找最小元，写回位置 \(i\)（本代码先记下最小值与下标，再一次性写入，交换次数少）。
比较次数始终是 \(\frac{n(n-1)}{2}\)，与输入无关，故所有情况时间均为 \(O(n^2)\)；交换次数至多 \(n-1\)，为 \(O(n)\)。
辅助空间 \(O(1)\)。
不稳定：把后面选到的最小元与前面位置对换，可能打乱相等关键字的相对顺序（例如 5a 5b 1，第一轮会把 1 与 5a 对换）。

package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&arr[i])
	}
	for i := 0; i < n-1; i++ {
		var smallestNum int = arr[i]
		var smallestIndex int = i
		for j := i + 1; j < n; j++ {
			if smallestNum > arr[j] {
				smallestNum = arr[j]
				smallestIndex = j
			}
		}
		arr[smallestIndex] = arr[i]
		arr[i] = smallestNum
	}
	for i := 0; i < n; i++ {
		fmt.Printf("%v ", arr[i])
	}
	fmt.Println("")
}

3-插入排序

每次从未排序区间取出一个元素，插入到已排序区间中的正确位置（本实现用搬运而不是逐次交换）。

原理与复杂度：

对近乎有序的输入非常高效：每个元素只需向左移动很少位置。可用逆序对个数理解：元素移动次数大致等于它所参与的逆序对数量。
最佳情况（已有序）：每个元素只比较一次，时间 \(O(n)\)；
平均、最坏情况：逆序对可到 \(\Theta(n^2)\) 量级，时间 \(O(n^2)\)。有两层 for 不等于所有输入都是 \(n^2\)——已有序时内层几乎不执行。
辅助空间 \(O(1)\)；稳定（只在严格大于时搬运，相等元素不越过彼此）。

package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&arr[i])
	}
	for i := 1; i < n; i++ {
		temp := arr[i]
		j := i - 1
		for j >= 0 && arr[j] > temp {
			arr[j+1] = arr[j]
			j--
		}
		arr[j+1] = temp
	}
	for i := 0; i < n; i++ {
		fmt.Printf("%v ", arr[i])
	}
	fmt.Println("")
}

4-希尔排序

希尔排序是对插入排序的优化。插入排序慢，是因为相隔很远的“较小元素”要一步步向左搬。希尔排序引入 gap（增量）：让下标相差 gap 的元素组成同一逻辑子序列，在各子序列上做插入排序；再逐步缩小 gap，最终 gap = 1 退化为一次完整插入排序，从而保证整体有序。

需要澄清：

所谓“分组”是逻辑上的：同余下标（模 gap 同余）构成一条子序列，并不会真正分配若干子数组。
本实现的增量序列为 \(n/2\) 连续折半：\(\lfloor n/2 \rfloor, \lfloor n/4 \rfloor, \ldots, 1\)。
gap 最终变为 \(1\)，因此算法一定能完成排序。

复杂度（针对本实现的折半增量，与文献中其他增量序列的结论不同）：

一个 gap 的一趟中，扫描本身是 \(O(n)\)；输入已有序时内层搬运不发生，一趟合计 \(O(n)\)，但外层仍要走完，故最佳也是 \(O(n \log n)\)。一般输入下每趟还包含插入搬运，一趟可达二次量级。共有 \(O(\log n)\) 个 gap。
最坏情况 \(O(n^2)\)。
平均情况依赖增量序列与输入分布，不能给所有希尔排序实现套用同一个平均复杂度。折半增量在不少输入上能减少搬运，但仍有二次时间的最坏情况。
辅助空间 \(O(1)\)；不稳定（跨 gap 的搬运可能改变相等元素相对顺序）。

package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&arr[i])
	}
	for gap := n / 2; gap >= 1; gap /= 2 {
		for i := gap; i < n; i++ {
			temp := arr[i]
			j := i
			for j >= gap && arr[j-gap] > temp {
				arr[j] = arr[j-gap]
				j -= gap
			}
			arr[j] = temp
		}
	}
	for i := 0; i < n; i++ {
		fmt.Printf("%v ", arr[i])
	}
	fmt.Println()
}

5-归并排序

归并排序的核心：单个元素天然有序；若已有两个有序序列，把它们合并成一个有序序列很容易。于是递归把区间拆到长度为 \(1\) 的有序段，再一层层合并回去。

本实现的特点：

每一层的 merge 都是线性合并，没有“某侧已整体有序就直接接上”的跳过优化。
因此各种典型情况（最好、平均、最坏）时间都是 \(O(n \log n)\)：每层合并总计 \(O(n)\)，共 \(O(\log n)\) 层。
稳定性：比较写成 left[i] <= right[j] 时优先取左，相等元素保持相对顺序，故稳定。
arr[:mid] 等切片只是创建新切片头，不会立刻复制底层数据；真正成规模的额外数组来自 merge 中的 output。

辅助空间要区分“峰值”与“累计”：

峰值同时活跃的辅助空间：output 等约 \(O(n)\)，加上递归栈 \(O(\log n)\)，合计 \(O(n)\) 量级。
整个执行过程中累计分配量可以是 \(O(n \log n)\)，但这不等于峰值辅助空间。Go 的堆分配还受 GC 影响，实测内存曲线不宜直接当理论辅助空间。

补充（链表归并，仅原理）：单链表归并不需要数组那样的 output，合并时直接连接节点即可；二分可以靠快慢指针找中点。递归版栈深 \(O(\log n)\)；若改成自底向上迭代归并，指针辅助空间可到 \(O(1)\)（不含链表本身）。

package main

import "fmt"

func mergeSort(arr []int) []int {
	if len(arr) <= 1 {
		return arr
	}
	mid := len(arr) / 2
	left := mergeSort(arr[:mid])
	right := mergeSort(arr[mid:])
	return merge(left, right)
}

func merge(left []int, right []int) []int {
	index1, index2 := 0, 0
	output := make([]int, len(left)+len(right))
	for index1 < len(left) && index2 < len(right) {
		if left[index1] <= right[index2] {
			output[index1+index2] = left[index1]
			index1++
		} else {
			output[index1+index2] = right[index2]
			index2++
		}
	}
	for index1 < len(left) {
		output[index1+index2] = left[index1]
		index1++
	}
	for index2 < len(right) {
		output[index1+index2] = right[index2]
		index2++
	}
	return output
}

func main() {
	var n int
	fmt.Scan(&n)
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&arr[i])
	}
	result := mergeSort(arr)
	for i := 0; i < n; i++ {
		fmt.Printf("%v ", result[i])
	}
	fmt.Println()
}

6-快速排序

本实现是 Lomuto 分区，固定取最右端为 pivot：

扫描时把小于 pivot 的元素换到左侧；大于等于 pivot 的留在右区。
区间不变量（一轮 Partition 过程中）：
- \([left, i)\)：元素 \(<\) pivot；
- \([i, j)\)：元素 \(\ge\) pivot；
- \([j, right)\)：尚未处理。
扫描结束后，把 pivot 与 \(i\) 处元素交换，此时 \(i\) 就是 pivot 排序后的最终位置；左右子区间递归。

复杂度与稳定性：

划分均衡时最好也是 \(O(n \log n)\)；平均情况：在互异关键字的随机排列模型下，期望时间 \(O(n \log n)\)。
本算法固定取最右端为 pivot，没有随机 pivot：输入已有序、完全逆序、或重复项很多（如全部相等）时划分极度不均，最坏 \(O(n^2)\)。
辅助空间：分区自身 \(O(1)\)，递归栈均衡时 \(O(\log n)\)、最坏 \(O(n)\)，并非 \(0\)。
不稳定：分区对换会打乱相等元素相对顺序。

package main

import "fmt"

func QuickSort(arr []int, left int, right int) {
	if left >= right {
		return
	}
	pivotIndex := Partition(arr, left, right)
	QuickSort(arr, left, pivotIndex-1)
	QuickSort(arr, pivotIndex+1, right)
}

func Partition(arr []int, left int, right int) int {
	pivot := arr[right]
	i, j := left, left
	for ; j < right; j++ {
		if arr[j] < pivot {
			arr[i], arr[j] = arr[j], arr[i]
			i++
		}
	}
	arr[i], arr[right] = arr[right], arr[i]
	return i
}

func main() {
	var n int
	fmt.Scan(&n)
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&arr[i])
	}
	QuickSort(arr, 0, len(arr)-1)
	for i := 0; i < n; i++ {
		fmt.Printf("%d ", arr[i])
	}
	fmt.Println()
}

7-堆排序

堆排序利用二叉堆组织数据。大顶堆要求：

是一棵完全二叉树（数组层序存放即可，不必显式建树）；
每个父节点的关键字 大于等于 其孩子。

这样堆顶一定是当前堆里的最大值。

大顶堆示例（文字版）：按层序排列的数组为 \([9, 7, 8, 3, 2, 5]\)，各节点关系如下：

节点值	左孩子	右孩子
9（根节点）	7	8
7	3	2
8	5	无
3、2、5（叶节点）	无	无

根节点为 \(9\)，第二层从左到右是 \(7、8\)，第三层从左到右是 \(3、2、5\)。节点依次占满最后一层左侧的位置，满足完全二叉树要求；同时 \(9 \ge 7\)、\(9 \ge 8\)、\(7 \ge 3\)、\(7 \ge 2\)、\(8 \ge 5\)，所有父节点均不小于其孩子，因此这是合法的大顶堆。

用数组表示堆时，按层序从上到下、从左到右编号。若节点下标为 \(i\)，则：

左孩子：\(2i+1\)（若 \(< n\)）；
右孩子：\(2i+2\)（若 \(< n\)）；
父节点：\(\lfloor (i-1)/2 \rfloor\)，仅当 \(i > 0\)；根节点没有父节点。

排序思路：

建堆：自底向上把数组调整成大顶堆，最大值落到 arr[0]；
排序：把堆顶最大值换到当前范围末尾，范围缩小 \(1\)，再对新的堆顶做 heapify 修复。重复直到范围为 \(1\)。

heapify（下沉）的前提是：以 \(i\) 的左右孩子为根的两棵子树都已满足堆性质；若当前根不满足堆性质，就与较大的孩子交换并继续下沉。建堆时从 \(n/2-1\) 扫到 \(0\)，先让较低的子树成堆，再处理上层节点。因此，初始无序数组不能只调用一次 heapify(0) 就完成建堆。

下沉调整示例（文字版）：初始父节点是 \(4\)，左孩子是 \(10\)，右孩子是 \(3\)。

调整阶段	父节点	左孩子	右孩子	层序数组
交换前	4	10	3	\([4, 10, 3]\)
交换后	10	4	3	\([10, 4, 3]\)

判断堆性质：\(10 > 4\)，左孩子大于父节点，因此初始结构不是大顶堆。
选择较大的孩子：两个孩子中 \(10 > 3\)，所以将父节点 \(4\) 与较大的孩子 \(10\) 交换。
检查结果：交换后父节点为 \(10\)，左孩子为 \(4\)，右孩子仍为 \(3\)。此时 \(10 \ge 4\) 且 \(10 \ge 3\)，这个仅有三个节点的示例恢复了大顶堆性质。

在更大的堆中，若下沉后的 \(4\) 还有孩子，则继续在它所在的子树中比较并下沉，直到满足堆性质。

package main

import "fmt"

func heapify(arr []int, n int, i int) {
	largest := i
	left := 2*i + 1
	right := 2*i + 2
	if left < n && arr[left] > arr[largest] {
		largest = left
	}
	if right < n && arr[right] > arr[largest] {
		largest = right
	}
	if largest != i {
		arr[i], arr[largest] = arr[largest], arr[i]
		heapify(arr, n, largest)
	}
}

func heapSort(arr []int) {
	n := len(arr)
	for i := n/2 - 1; i >= 0; i-- {
		//n/2-1是最大的有孩子的节点
		heapify(arr, n, i) //从下往上建立
	}
	for i := n - 1; i > 0; i-- {
		arr[0], arr[i] = arr[i], arr[0]
		heapify(arr, i, 0) //修复堆顶
	}
}

func main() {
	var n int
	fmt.Scan(&n)
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&arr[i])
	}
	heapSort(arr)
	for i := 0; i < n; i++ {
		fmt.Printf("%d ", arr[i])
	}
	fmt.Println()
}

与实现对应的复杂度：

单次 heapify 是沿树高下沉，时间上界 \(O(\log n)\)。
自底向上建堆是 \(O(n)\)（不是 \(n \log n\)）：高度为 \(h\) 的节点只有 \(O(n/2^{h+1})\) 个，每个至多下沉 \(h\) 层，总下沉工作为 \(O\left(n \sum_{h \ge 0} h/2^{h}\right) = O(n)\)——底层节点多但下沉浅。
排序阶段反复取出最大值，最坏与平均 \(O(n \log n)\)；若全部关键字相等，本代码的下沉几乎不发生，最好可到 \(O(n)\)。
辅助空间：本代码用递归 heapify，最坏栈深 \(O(\log n)\)；若改成迭代下沉，辅助空间才降为 \(O(1)\)，故本实现的辅助空间是 \(O(\log n)\) 而非 \(0\)。
不稳定：堆顶与末尾交换会打乱相等元素顺序。

8-计数排序

思想：把“值本身”当作下标统计出现次数，最后按值从小到大读出。

package main

import "fmt"

func countingSort(arr []int, maxValue int) {
	indexArr := make([]int, maxValue+1)
	n := len(arr)
	for i := 0; i < n; i++ {
		indexArr[arr[i]+maxValue/2]++
	}
	j := 0
	for i := 0; i < n; i++ {
		for indexArr[j] == 0 {
			j++
		}
		indexArr[j]--
		arr[i] = j - maxValue/2
	}
}

func main() {
	var n int
	fmt.Scan(&n)
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&arr[i])
	}
	countingSort(arr, 512)
	for i := 0; i < n; i++ {
		fmt.Printf("%d ", arr[i])
	}
	fmt.Println()
}

针对本实现：

maxValue 传入 \(512\)，indexArr 分配 \(513\) 项，写入下标是 arr[i] + 256，即值域偏移 \(256\)，可容纳 \([-256, 256]\)。若输入超出该范围会下标越界。
设 \(k\) 为值域宽度（本例固定 \(k = 513\)）。重建阶段 \(j\) 单调向右、不反复从头扫描，时间 \(O(n + k)\)；本例 \(k\) 为常数时可写成关于 \(n\) 的线性。辅助空间 \(O(k)\)。
注意稳定性：本实现按频次直接重建排序后的值，没有携带原记录的身份，不能据此承诺相等记录的顺序得到保留。常规的稳定计数排序先由频次算出累计计数（各关键字的结束位置），再逆向扫描原记录、依次递减结束位置并写入 output。后出现的相等记录落在更靠右的位置，因此最终保持原相对顺序；时间为 \(O(n + k)\)，辅助空间为 \(O(n + k)\)。

9-桶排序

思路：按关键字大小把元素分到 \(b\) 个桶，每个桶内再排序，最后按桶顺序拼接。本实现固定 \(b = 8\)，桶内使用 slices.Sort。

package main

import (
	"fmt"
	"slices"
)

func bucketSort(arr []int) {
	if len(arr) <= 0 {
		return
	}
	bucketCount := 8
	buckets := make([][]int, bucketCount)
	minVal, maxVal := arr[0], arr[0]
	for index := range arr {
		if minVal > arr[index] {
			minVal = arr[index]
		}
		if maxVal < arr[index] {
			maxVal = arr[index]
		}
	}
	for arrIndex := range arr {
		index := (arr[arrIndex] - minVal) * bucketCount / (maxVal - minVal + 1)
		buckets[index] = append(buckets[index], arr[arrIndex])
	}
	i := 0
	for index := range buckets {
		slices.Sort(buckets[index])
		for _, value := range buckets[index] {
			arr[i] = value
			i++
		}
	}
}

func main() {
	var n int
	fmt.Scan(&n)
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&arr[i])
	}
	bucketSort(arr)
	for i := 0; i < n; i++ {
		fmt.Printf("%d ", arr[i])
	}
	fmt.Println()
}

复杂度（对应固定 8 桶 + 桶内比较排序）：

记第 \(j\) 个桶内元素个数为 \(m_j\)。分桶扫描 \(O(n)\)，求最值 \(O(n)\)，写入 \(b\) 个桶头开销 \(O(b)\)，桶内排序合计 \(O\bigl(\sum_j m_j \log (m_j+1)\bigr)\)。
时间上界可写为 \(O\bigl(n + b + \sum_j m_j \log (m_j+1)\bigr)\)。若关键字在区间上大致均匀，各桶大小接近 \(n/b\)，得到上界 \(O\bigl(n \log(n/b+1) + n + b\bigr)\)。
本实现 \(b = 8\) 为常数，平均与最坏上界仍是 \(O(n \log n)\) 量级，不是教科书中“\(b\) 随 \(n\) 增长时期望线性”的那一类结论。全部元素相等时，每个桶可视为近似有序，slices.Sort 可接近线性。
辅助空间 \(O(n + b)\)（所有桶合计装下全部元素，外加桶头）。
稳定性：桶内 slices.Sort 不稳定，因此整体不稳定。
负数：先减 minVal 再分桶，负数可正常处理。极端大整数时，maxVal - minVal + 1 或与 bucketCount 相乘存在溢出风险。

10-基数排序

思想：按位排序，从个位起由低到高（LSD）。每一位都做一轮稳定的计数排序，从而高位相同的元素得以保持已经建立的低位顺序。

package main

import (
	"fmt"
)

func radixSort(arr []int) {
	if len(arr) <= 1 {
		return
	}
	maxValue := 0
	for _, val := range arr {
		if val < 0 {
			return
		}
		if val > maxValue {
			maxValue = val
		}
	}
	output := make([]int, len(arr))
	for exp := 1; exp <= maxValue; exp *= 10 {
		countArr := make([]int, 10)
		for _, v := range arr {
			digit := (v / exp) % 10
			countArr[digit]++
		}
		for i := 1; i < 10; i++ {
			countArr[i] += countArr[i-1]
		}
		for i := len(arr) - 1; i >= 0; i-- {
			digit := (arr[i] / exp) % 10
			countArr[digit]--
			output[countArr[digit]] = arr[i]
		}
		copy(arr, output)
		if exp > maxValue/10 {
			break
		}
	}
}
func main() {
	var n int
	fmt.Scan(&n)
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&arr[i])
	}
	radixSort(arr)
	for i := 0; i < n; i++ {
		fmt.Printf("%d ", arr[i])
	}
	fmt.Println()
}

针对本实现：

从 exp = 1 开始，每位取 \(\lfloor v/exp \rfloor \bmod 10\)；这里的 Go 整数除法对非负数等价于向下取整，基数 \(r = 10\)。
一轮内：先统计各位频次，再做前缀和——前缀和表示“小于等于该位数字的个数”；然后从后向前扫描原数组写入 output，这样同一数字的关键字相对顺序不变，该轮计数排序是稳定的。每一轮都稳定，高位相同的元素才不会打乱已经建立的低位顺序，整体排序才是稳定的。
设数字位数为 \(d\)，时间 \(O\bigl(d(n + r)\bigr)\)，辅助空间 \(O(n + r)\)（output 与计数数组）。
稳定（在能处理的输入上）。
限制：
- 遇到负数直接 return，不能宣称支持所有整数；
- 全为 \(0\) 时 exp <= maxValue 不成立，一次位循环都不执行，时间只有扫描求 maxValue 的 \(O(n)\)，辅助空间仍为 \(O(n + r)\)；
- 循环末尾的 if exp > maxValue/10 { break } 用于防止 exp *= 10 溢出，是有作用的防护。

总览与选用建议

下表按本文具体实现汇总；空间列给出辅助空间的上界，递归栈也计入其中。\(k\) 是值域宽度，\(b\) 是桶数，\(d\) 是位数，\(r\) 是基数。

算法	最佳 / 平均 / 最坏时间	本文辅助空间	稳定性	与标准结论的差异、适用限制
冒泡	\(O(n)\) / \(O(n^2)\) / \(O(n^2)\)	\(O(1)\)	稳定	提前终止但边界不收缩；教学入门用
选择	\(O(n^2)\) / \(O(n^2)\) / \(O(n^2)\)	\(O(1)\)	不稳定	比较次数固定 \(\frac{n(n-1)}{2}\)；交换少
插入	\(O(n)\) / \(O(n^2)\) / \(O(n^2)\)	\(O(1)\)	稳定	近乎有序时接近线性；小规模或基本有序首选
希尔	\(O(n \log n)\) / 依赖输入分布与增量 / \(O(n^2)\)	\(O(1)\)	不稳定	本文采用折半增量；不同增量序列的界不同
归并	\(O(n \log n)\) 三情况皆是	峰值 \(O(n)\)（栈 \(O(\log n)\)）	稳定	无“已排序跳过”优化；链表归并可省去数组 `output`
快排	\(O(n \log n)\) / 期望 \(O(n \log n)\) / \(O(n^2)\)	分区 \(O(1)\)，栈 \(O(\log n)\)–\(O(n)\)	不稳定	固定最右 Lomuto；有序/逆序/重复项多退化；期望列对应互异关键字随机排列
堆排	\(O(n)\)（全等）/ \(O(n \log n)\) / \(O(n \log n)\)	递归栈 \(O(\log n)\)	不稳定	建堆 \(O(n)\)；迭代 heapify 才 \(O(1)\) 辅助
计数	\(O(n+k)\)	\(O(k)\)	本实现不保留记录顺序	值域必须已知且不大；越界会崩；稳定版需累计计数配合逆向扫描
桶排	均匀分桶上界 \(O(n\log(n/b+1)+n+b)\)；固定 \(b=8\) 平均、最坏上界 \(O(n \log n)\)	\(O(n+b)\)	不稳定	桶内 `slices.Sort`；固定桶数不能保证期望线性
基数	\(O(d(n+r))\)	\(O(n+r)\)	稳定	LSD + 稳定计数；负数不支持；全 0 时间 \(O(n)\)、空间仍 \(O(n+r)\)

选用建议：

小规模或基本有序的数据：插入排序实现简单，搬运开销通常较小；冒泡、选择适合学习相邻交换与每轮选择最值的思路。
通用比较排序、要稳定：归并排序（可链表、可外部排序）。
通用比较排序：快速排序的分区开销小，在互异关键字随机排列下期望为 \(O(n \log n)\)。本文固定最右枢轴，已有序或大量重复数据可能退化；随机枢轴能缓解有序输入带来的退化，重复值还需要合适的分区策略。
要最坏也是 \(O(n \log n)\) 且不开大数组：堆排序（递归版有 \(O(\log n)\) 栈）。
值域小的整数：计数排序（\(k\) 大时不如比较排序）。
大致均匀、可映射到区间：桶排序（桶数与桶内算法影响很大）。
定长整数位、且非负：基数排序（位数少、范围宽时优势明显）。