排序算法

排序是计算机科学中最经典、研究最深入的问题之一。虽然工程中我们几乎都用标准库的排序函数，但理解各种排序算法的原理、复杂度、稳定性，对面试和算法设计能力都至关重要——很多算法的思想（分治、贪心、堆）都会在排序中首次亮相。本篇将系统梳理 O(n²)、O(n log n)、O(n) 三大类排序算法，对比它们的优劣，并深入讲解 Go 标准库 sort / slices 包的内部实现（pdqsort），最后演示自定义排序规则。

一、排序算法分类

排序算法可以从多个维度分类：

按时间复杂度：O(n²) 的冒泡、选择、插入；O(n log n) 的快排、归并、堆排；O(n) 的计数、基数、桶排序。
按是否原地：原地排序（快排、堆排）vs 非原地（归并、计数）。
按稳定性：稳定排序（冒泡、插入、归并）vs 不稳定（选择、快排、堆排）。稳定性指相等元素排序后相对顺序不变。
按分治与否：快排、归并是分治；冒泡、选择、插入是直接比较。

选择排序算法时，要综合考虑数据规模、是否需稳定、数据分布、内存限制。

二、O(n²) 排序

1. 冒泡排序

相邻元素两两比较，每轮把最大元素「冒泡」到末尾。可优化：若某轮无交换则已有序。

package main

import "fmt"

func bubbleSort(nums []int) {
	n := len(nums)
	for i := 0; i < n-1; i++ {
		swapped := false
		for j := 0; j < n-1-i; j++ {
			if nums[j] > nums[j+1] {
				nums[j], nums[j+1] = nums[j+1], nums[j]
				swapped = true
			}
		}
		if !swapped {
			break
		}
	}
}

func main() {
	nums := []int{64, 34, 25, 12, 22, 11, 90}
	bubbleSort(nums)
	fmt.Println("冒泡排序:", nums)
}

时间：最好 O(n)（已有序），平均/最坏 O(n²)。
空间：O(1)，稳定。

2. 选择排序

每轮从未排序部分选最小值，与未排序部分首位交换。

package main

import "fmt"

func selectionSort(nums []int) {
	n := len(nums)
	for i := 0; i < n-1; i++ {
		minIdx := i
		for j := i + 1; j < n; j++ {
			if nums[j] < nums[minIdx] {
				minIdx = j
			}
		}
		nums[i], nums[minIdx] = nums[minIdx], nums[i]
	}
}

func main() {
	nums := []int{64, 34, 25, 12, 22, 11, 90}
	selectionSort(nums)
	fmt.Println("选择排序:", nums)
}

时间：始终 O(n²)（无论数据分布）。
空间：O(1)，不稳定（交换可能改变相等元素顺序）。

3. 插入排序

把每个元素插入到已排序部分的正确位置。对小规模或近似有序数据非常高效。

package main

import "fmt"

func insertionSort(nums []int) {
	for i := 1; i < len(nums); i++ {
		key := nums[i]
		j := i - 1
		for j >= 0 && nums[j] > key {
			nums[j+1] = nums[j]
			j--
		}
		nums[j+1] = key
	}
}

func main() {
	nums := []int{64, 34, 25, 12, 22, 11, 90}
	insertionSort(nums)
	fmt.Println("插入排序:", nums)
}

时间：最好 O(n)（已有序），平均/最坏 O(n²)。
空间：O(1)，稳定。
实践中，小数组（n < 16 左右）插入排序常被用作快排、归并的底层实现。

三、O(n log n) 排序

1. 快速排序

选一个基准（pivot），把小于基准的放左、大于的放右，递归排序左右两部分。平均 O(n log n)，最坏 O(n²)（已有序且选首元素为基准），可通过随机化基准规避。

package main

import (
	"fmt"
	"math/rand"
)

func quickSort(nums []int) {
	if len(nums) <= 1 {
		return
	}
	// 随机选基准，避免最坏情况
	pivotIdx := rand.Intn(len(nums))
	nums[pivotIdx], nums[len(nums)-1] = nums[len(nums)-1], nums[pivotIdx]
	pivot := nums[len(nums)-1]

	// 三路划分：<pivot | =pivot | >pivot
	lt, gt := 0, len(nums)-1
	i := 0
	for i <= gt {
		if nums[i] < pivot {
			nums[i], nums[lt] = nums[lt], nums[i]
			lt++
			i++
		} else if nums[i] > pivot {
			nums[i], nums[gt] = nums[gt], nums[i]
			gt--
		} else {
			i++
		}
	}
	quickSort(nums[:lt])
	quickSort(nums[gt+1:])
}

func main() {
	nums := []int{3, 6, 8, 10, 1, 2, 1}
	quickSort(nums)
	fmt.Println("快速排序:", nums)
}

三路划分（Dutch National Flag）能高效处理大量重复元素，是工程快排的常见优化。

2. 归并排序

分治：把数组对半切，递归排序两半，再合并两个有序数组。稳定，但需要 O(n) 额外空间。

package main

import "fmt"

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

func merge(left, right []int) []int {
	result := make([]int, 0, len(left)+len(right))
	i, j := 0, 0
	for i < len(left) && j < len(right) {
		if left[i] <= right[j] {
			result = append(result, left[i])
			i++
		} else {
			result = append(result, right[j])
			j++
		}
	}
	result = append(result, left[i:]...)
	result = append(result, right[j:]...)
	return result
}

func main() {
	nums := []int{38, 27, 43, 3, 9, 82, 10}
	fmt.Println("归并排序:", mergeSort(nums))
}

归并排序的链表版本可以做到 O(1) 额外空间，是链表排序的首选。

3. 堆排序

建大顶堆 O(n)，然后不断交换堆顶与末尾、下沉。原地排序，但不稳定，且缓存局部性差（跳跃式访问）。

package main

import "fmt"

func heapSort(nums []int) {
	n := len(nums)
	for i := n/2 - 1; i >= 0; i-- {
		siftDown(nums, i, n)
	}
	for i := n - 1; i > 0; i-- {
		nums[0], nums[i] = nums[i], nums[0]
		siftDown(nums, 0, i)
	}
}

func siftDown(nums []int, i, n int) {
	for {
		left := 2*i + 1
		right := 2*i + 2
		largest := i
		if left < n && nums[left] > nums[largest] {
			largest = left
		}
		if right < n && nums[right] > nums[largest] {
			largest = right
		}
		if largest == i {
			break
		}
		nums[i], nums[largest] = nums[largest], nums[i]
		i = largest
	}
}

func main() {
	nums := []int{12, 11, 13, 5, 6, 7}
	heapSort(nums)
	fmt.Println("堆排序:", nums)
}

四、O(n) 排序

这类排序不基于比较，能突破 O(n log n) 的下界，但对待排序数据有特定要求（如范围已知）。

1. 计数排序

适合元素范围不大的整数排序。统计每个值出现次数，再前缀和确定位置。

package main

import "fmt"

func countingSort(nums []int) []int {
	if len(nums) == 0 {
		return nums
	}
	minVal, maxVal := nums[0], nums[0]
	for _, v := range nums {
		if v < minVal {
			minVal = v
		}
		if v > maxVal {
			maxVal = v
		}
	}
	range_ := maxVal - minVal + 1
	count := make([]int, range_)
	for _, v := range nums {
		count[v-minVal]++
	}
	// 前缀和（让排序稳定）
	for i := 1; i < len(count); i++ {
		count[i] += count[i-1]
	}
	output := make([]int, len(nums))
	for i := len(nums) - 1; i >= 0; i-- {
		v := nums[i]
		count[v-minVal]--
		output[count[v-minVal]] = v
	}
	return output
}

func main() {
	nums := []int{4, 2, 2, 8, 3, 3, 1}
	fmt.Println("计数排序:", countingSort(nums))
}

时间 O(n + k)，空间 O(k)，k 是值域大小。稳定（前缀和 + 逆序填充）。

2. 基数排序

按位（个、十、百……）从低到高，每位用计数排序。适合位数固定的整数或字符串。

package main

import "fmt"

func radixSort(nums []int) {
	if len(nums) == 0 {
		return
	}
	maxVal := nums[0]
	for _, v := range nums {
		if v > maxVal {
			maxVal = v
		}
	}
	for exp := 1; maxVal/exp > 0; exp *= 10 {
		countingSortByDigit(nums, exp)
	}
}

func countingSortByDigit(nums []int, exp int) {
	n := len(nums)
	output := make([]int, n)
	count := make([]int, 10)
	for i := 0; i < n; i++ {
		digit := (nums[i] / exp) % 10
		count[digit]++
	}
	for i := 1; i < 10; i++ {
		count[i] += count[i-1]
	}
	for i := n - 1; i >= 0; i-- {
		digit := (nums[i] / exp) % 10
		count[digit]--
		output[count[digit]] = nums[i]
	}
	copy(nums, output)
}

func main() {
	nums := []int{170, 45, 75, 90, 802, 24, 2, 66}
	radixSort(nums)
	fmt.Println("基数排序:", nums)
}

时间 O(d·(n+k))，d 是位数，k 是基数（通常 10）。稳定。

3. 桶排序

把元素分到若干桶，每个桶内排序后合并。适合数据均匀分布的场景。

package main

import (
	"fmt"
	"sort"
)

func bucketSort(nums []float64) []float64 {
	if len(nums) == 0 {
		return nums
	}
	minVal, maxVal := nums[0], nums[0]
	for _, v := range nums {
		if v < minVal {
			minVal = v
		}
		if v > maxVal {
			maxVal = v
		}
	}
	bucketCount := len(nums)
	buckets := make([][]float64, bucketCount)
	for _, v := range nums {
		idx := int((v - minVal) / (maxVal - minVal) * float64(bucketCount-1))
		buckets[idx] = append(buckets[idx], v)
	}
	result := make([]float64, 0, len(nums))
	for _, b := range buckets {
		sort.Float64s(b)
		result = append(result, b...)
	}
	return result
}

func main() {
	nums := []float64{0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12}
	fmt.Println("桶排序:", bucketSort(nums))
}

五、排序算法对比

算法	平均时间	最坏时间	空间	稳定	备注
冒泡	O(n²)	O(n²)	O(1)	稳定	最好 O(n)
选择	O(n²)	O(n²)	O(1)	不稳定	始终 O(n²)
插入	O(n²)	O(n²)	O(1)	稳定	小数组高效
快排	O(n log n)	O(n²)	O(log n)	不稳定	实践中最快
归并	O(n log n)	O(n log n)	O(n)	稳定	适合链表、外部排序
堆排	O(n log n)	O(n log n)	O(1)	不稳定	原地，最坏也是 O(n log n)
计数	O(n+k)	O(n+k)	O(k)	稳定	整数且范围小
基数	O(d(n+k))	O(d(n+k))	O(n+k)	稳定	位数固定
桶	O(n+k)	O(n²)	O(n+k)	稳定	数据均匀分布

各场景最优选择：

通用排序：用标准库（Go 的 pdqsort），已是工业级优化。
小数组（n < 16）：插入排序，常数小且稳定。
需要稳定：归并排序（或 Timsort）。
内存受限：堆排或原地快排。
整数且范围小：计数排序。
链表排序：归并排序。
外部排序（数据超内存）：归并排序。

六、Go 标准库排序

1. sort.Sort、sort.Slice

sort.Sort 需要实现 sort.Interface（Len/Less/Swap）；sort.Slice 用闭包更简洁。内部实现是 introsort（快排 + 堆排 + 插入排序的混合）。

package main

import (
	"fmt"
	"sort"
)

type Person struct {
	Name string
	Age  int
}

func main() {
	// sort.Slice：闭包式
	people := []Person{
		{"Alice", 30}, {"Bob", 25}, {"Charlie", 35},
	}
	sort.Slice(people, func(i, j int) bool {
		return people[i].Age < people[j].Age
	})
	fmt.Println("按年龄升序:", people)

	// sort.Sort：接口式
	type ByAge []Person
	// （省略方法定义，思路同 sort 包介绍篇）
	_ = sort.Sort
}

2. slices.Sort（泛型，Go 1.21+）

slices 包提供类型安全的泛型排序，是 Go 1.21+ 项目的首选。

package main

import (
	"fmt"
	"slices"
)

func main() {
	nums := []int{5, 2, 8, 1, 9, 3}
	slices.Sort(nums)
	fmt.Println("slices.Sort:", nums)

	type Person struct {
		Name string
		Age  int
	}
	people := []Person{
		{"Alice", 30}, {"Bob", 25}, {"Charlie", 35},
	}
	slices.SortFunc(people, func(a, b Person) int {
		return a.Age - b.Age
	})
	fmt.Println("泛型排序:", people)

	// slices.IsSorted 判断有序
	fmt.Println("是否有序:", slices.IsSorted(nums))

	// slices.Stable 稳定排序
	slices.Stable(nums)
	fmt.Println("稳定排序:", nums)
}

3. 内部实现：pdqsort

Go 1.19 起，sort 和 slices 包内部使用 pdqsort（Pattern-Defeating Quicksort），它结合了多种策略：

小数组（≤ 12）用插入排序。
中等数组用快速排序，pivot 选择用「median of three」或随机。
发现数据近似有序或快排递归过深时切换到堆排序（避免最坏 O(n²)）。
检测到某些模式（如已部分有序）会切换到插入排序。

pdqsort 对各种数据分布都有不错的表现：随机数据接近快排速度，近似有序数据接近插入排序，最坏情况也有 O(n log n) 保证。这是目前工业界最先进的通用排序之一（Rust、C++ 标准库也采用类似思路）。

七、实战：自定义排序规则

工程中经常需要按复杂规则排序：多字段、升降混合、按计算值。下面演示几种常见模式：

package main

import (
	"fmt"
	"sort"
)

type Student struct {
	Name string
	Age  int
	Score float64
}

func main() {
	students := []Student{
		{"Alice", 20, 88.5},
		{"Bob", 22, 75.0},
		{"Charlie", 20, 95.0},
		{"David", 22, 88.5},
	}

	// 1. 按分数降序
	sort.Slice(students, func(i, j int) bool {
		return students[i].Score > students[j].Score
	})
	fmt.Println("分数降序:", students)

	// 2. 多字段：年龄升序，年龄相同按分数降序
	sort.Slice(students, func(i, j int) bool {
		if students[i].Age != students[j].Age {
			return students[i].Age < students[j].Age
		}
		return students[i].Score > students[j].Score
	})
	fmt.Println("年龄升序+分数降序:", students)

	// 3. 按计算值排序：按姓名长度
	sort.Slice(students, func(i, j int) bool {
		return len(students[i].Name) < len(students[j].Name)
	})
	fmt.Println("姓名长度升序:", students)

	// 4. 字符串切片自定义排序：忽略大小写
	words := []string{"Banana", "apple", "Cherry", "date"}
	sort.Slice(words, func(i, j int) bool {
		return stringsToLower(words[i]) < stringsToLower(words[j])
	})
	fmt.Println("忽略大小写:", words)
}

func stringsToLower(s string) string {
	result := make([]byte, len(s))
	for i := 0; i < len(s); i++ {
		c := s[i]
		if c >= 'A' && c <= 'Z' {
			c += 'a' - 'A'
		}
		result[i] = c
	}
	return string(result)
}

自定义排序的核心是写好 Less 函数（返回 true 表示 i 应排在 j 前）。多字段排序时，先用第一个字段比较，相等再比第二个，依此类推。

八、复杂度与稳定性实战总结

工程选型建议：

绝大多数场景：直接用 slices.Sort / sort.Slice，标准库已足够好。
需要稳定排序：用 slices.Stable / sort.SliceStable（基于 Timsort 思想）。
大数据量 + 整数：可考虑计数/基数排序突破 O(n log n)。
流式数据 / Top K：用堆（见堆与优先队列篇）。
自定义结构体：用 sort.Slice 闭包，最简洁。

九、小结

排序是算法学习的「必修课」，本篇要点：

O(n²) 排序：冒泡（稳定、可提前终止）、选择（不稳定、始终 O(n²)）、插入（稳定、小数组最优）。三者都是原地排序。
O(n log n) 排序：快排（平均最快、不稳定、最坏 O(n²) 可用随机化规避）、归并（稳定、需 O(n) 空间、适合链表和外部排序）、堆排（原地、最坏 O(n log n)、缓存差）。
O(n) 排序：计数（整数且范围小）、基数（位数固定）、桶（均匀分布）。都基于非比较，对数据有要求。
稳定性指相等元素相对顺序不变，影响多字段排序的正确性。需要稳定时选归并或标准库的 Stable 版本。
Go 标准库 sort.Slice 用闭包最简洁，slices.Sort（Go 1.21+）泛型更安全，内部都是 pdqsort——结合快排、堆排、插入排序的工业级混合算法。
自定义排序核心是写好 Less 函数，多字段排序用「先比第一字段，相等再比第二」的模式。

排序算法虽然「老生常谈」，但它蕴含的分治、贪心、堆的思想会在后续很多算法中复现。下一篇我们将进入动态规划——算法世界中最有挑战性、也最有成就感的领域。

入门篇

进阶篇

资深篇

排序算法

一、排序算法分类

二、O(n²) 排序

1. 冒泡排序

2. 选择排序

3. 插入排序

三、O(n log n) 排序

1. 快速排序

2. 归并排序

3. 堆排序

四、O(n) 排序

1. 计数排序

2. 基数排序

3. 桶排序

五、排序算法对比

六、Go 标准库排序

1. sort.Sort、sort.Slice

2. slices.Sort（泛型，Go 1.21+）

3. 内部实现：pdqsort

七、实战：自定义排序规则

八、复杂度与稳定性实战总结

九、小结

排序算法 ​

一、排序算法分类 ​

二、O(n²) 排序 ​

1. 冒泡排序 ​

2. 选择排序 ​

3. 插入排序 ​

三、O(n log n) 排序 ​

1. 快速排序 ​

2. 归并排序 ​

3. 堆排序 ​

四、O(n) 排序 ​

1. 计数排序 ​

2. 基数排序 ​

3. 桶排序 ​

五、排序算法对比 ​

六、Go 标准库排序 ​

1. sort.Sort、sort.Slice ​

2. slices.Sort（泛型，Go 1.21+） ​

3. 内部实现：pdqsort ​

七、实战：自定义排序规则 ​

八、复杂度与稳定性实战总结 ​

九、小结 ​

排序算法

一、排序算法分类

二、O(n²) 排序

1. 冒泡排序

2. 选择排序

3. 插入排序

三、O(n log n) 排序

1. 快速排序

2. 归并排序

3. 堆排序

四、O(n) 排序

1. 计数排序

2. 基数排序

3. 桶排序

五、排序算法对比

六、Go 标准库排序

1. sort.Sort、sort.Slice

2. slices.Sort（泛型，Go 1.21+）

3. 内部实现：pdqsort

七、实战：自定义排序规则

八、复杂度与稳定性实战总结

九、小结