第12章 排序算法
12.1 排序的基本概念
12.1.1 排序的定义
排序是将一组无序数据元素按关键字（如数值大小、字符编码）重新排列vb.net教程C#教程python教程SQL教程access 2010教程为递增或递减有序序列的过程。有序数据可显著提升查找（如二分查找）、统计等操作的效率，是数据处理的基础。
12.1.2 排序算法的评价指标
时间复杂度：排序过程中关键字比较次数和元素移动次数的量级，反映算法在不同数据规模下的效率（如O(n2)O(n^2)O(n2)、O(nlog⁡n)O(nlog n)O(nlogn)）。
空间复杂度：排序过程中额外占用的存储空间，分为原地排序（O(1)O(1)O(1)，无需额外数组）和非原地排序（如O(n)O(n)O(n)，需额外数组存储中间结果）。
稳定性：若排序后，相等元素的相对顺序保持不变（即原序列中ai=aja_i=a_jai​=aj​且i<ji<ji<j，排序后仍有i<ji<ji<j），则称算法稳定。
12.1.3 排序算法的分类
按排序过程中数据是否全部驻留内存，分为内排序（本章重点）和外排序（需借助外部存储）。内排序按核心操作可分为：
插入排序：直接插入排序、希尔排序；
交换排序：冒泡排序、快速排序；
选择排序：直接选择排序、堆排序；
归并排序：二路归并排序。
12.2 插入排序
12.2.1 直接插入排序
算法原理
核心思想：将无序序列中的元素逐个插入到有序序列的正确位置，直至整个序列有序。
步骤：
1.初始时，将第一个元素视为长度为1的有序序列；
2.对第iii（i=1,2,⋯ ,n−1i=1,2,cdots,n-1i=1,2,⋯,n−1）个元素，将其暂存为temptemptemp，与有序序列（前iii个元素）从后向前比较：
o若有序序列元素>temp>temp>temp，则后移该元素；
o否则，将temptemptemp插入到当前位置；
3.重复步骤2，直至所有元素插入完成。
示例
对数组[38,27,43,3,9,82,10][38,27,43,3,9,82,10][38,27,43,3,9,82,10]进行直接插入排序：
i=1i=1i=1（元素27）：有序序列[38][38][38]，27<38，插入后有序序列[27,38][27,38][27,38]；
i=2i=2i=2（元素43）：有序序列[27,38][27,38][27,38]，43>38，直接插入后[27,38,43][27,38,43][27,38,43]；
i=3i=3i=3（元素3）：有序序列[27,38,43][27,38,43][27,38,43]，3<27，插入后[3,27,38,43][3,27,38,43][3,27,38,43]；
后续步骤类推，最终结果[3,9,10,27,38,43,82][3,9,10,27,38,43,82][3,9,10,27,38,43,82]。
代码实现
python

	def direct_insertion_sort(arr): 
	n = len(arr) 
	for i in range(1, n): 
	temp = arr[i] # 当前待插入元素 
	j = i - 1 # 有序序列末尾索引 
	while j >= 0 and arr[j] > temp: 
	arr[j + 1] = arr[j] # 元素后移 
	j -= 1 
	arr[j + 1] = temp # 插入temp 
	return arr

性能分析

时间复杂度：

o最好情况（有序序列）：比较n−1n-1n−1次，移动0次，O(n)O(n)O(n)；
o最坏情况（逆序序列）：比较次数∑i=1n−1i=n(n−1)2sum_{i=1}^{{n-1}i=rac{n(n-1)}{2}∑i=1n−1​i=2n(n−1)​，移动次数同比较次数，O(n2)O(n}2)O(n2)；
o平均情况：O(n2)O(n^2)O(n2)。

空间复杂度：O(1)O(1)O(1)（仅需临时变量temptemptemp，原地排序）。


稳定性：稳定（相等元素不移动，相对顺序不变）。

适用场景
适用于小规模数据（n≤100nleq100n≤100）或基本有序序列（接近最好情况O(n)O(n)O(n)）。
12.2.2 希尔排序（缩小增量排序）
算法原理
核心思想：通过缩小增量将序列分成若干子序列，对各子序列进行直接插入排序；增量递减至1时，对整个序列进行一次直接插入排序。
增量序列：通常初始增量为gap=⌊n/2⌋gap=lfloor n/2 floorgap=⌊n/2⌋，之后gap=⌊gap/2⌋gap=lfloor gap/2 floorgap=⌊gap/2⌋，直至gap=1gap=1gap=1。
步骤
1.初始化增量gap=⌊n/2⌋gap=lfloor n/2 floorgap=⌊n/2⌋；
2.按增量gapgapgap将序列分为gapgapgap个子序列（索引i,i+gap,i+2gap,⋯i,i+gap,i+2gap,cdotsi,i+gap,i+2gap,⋯）；
3.对每个子序列进行直接插入排序；
4.缩小增量gap=⌊gap/2⌋gap=lfloor gap/2 floorgap=⌊gap/2⌋，重复步骤2~3，直至gap=1gap=1gap=1。
代码实现
python

	def shell_sort(arr): 
	n = len(arr) 
	gap = n // 2 # 初始增量 
	while gap > 0: 
	# 按增量gap对子序列插入排序 
	for i in range(gap, n): 
	temp = arr[i] 
	j = i - gap 
	while j >= 0 and arr[j] > temp: 
	arr[j + gap] = arr[j] 
	j -= gap 
	arr[j + gap] = temp 
	gap //= 2 # 缩小增量 
	return arr

性能分析
时间复杂度：依赖增量序列，常用增量下约为O(n1.3)O(n^{{1.3})O(n1.3)，最坏情况O(n2)O(n}2)O(n2)（如增量为1时退化为直接插入排序）。
空间复杂度：O(1)O(1)O(1)（原地排序）。
稳定性：不稳定（子序列排序可能破坏相等元素的相对顺序）。
适用场景
适用于中等规模数据（n=1000∼10000n=1000sim10000n=1000∼10000），效率优于直接插入排序。
12.3 交换排序
12.3.1 冒泡排序
算法原理
核心思想：通过相邻元素比较与交换，使大元素逐步“冒泡”至序列末尾。
步骤：
1.从序列起始位置开始，比较相邻元素，逆序则交换；
2.每轮遍历后，最大元素“冒泡”至当前未排序部分的末尾；
3.缩小未排序部分范围，重复步骤1~2，直至未排序部分长度为1。
优化策略
若某轮遍历未发生交换，说明序列已有序，可提前退出（减少无效遍历）。
代码实现（优化版）
python

	def bubble_sort(arr): 
	n = len(arr) 
	for i in range(n - 1): 
	swapped = False # 标记是否交换 
	for j in range(n - 1 - i): 
	if arr[j] > arr[j + 1]: 
	arr[j], arr[j + 1] = arr[j + 1], arr[j] 
	swapped = True 
	if not swapped: # 未交换，序列有序，提前退出 
	break 
	return arr

性能分析
时间复杂度：
o最好情况（有序序列，优化后）：O(n)O(n)O(n)（仅1轮遍历）；
o最坏情况（逆序序列）：O(n2)O(n^2)O(n2)；
o平均情况：O(n2)O(n^2)O(n2)。
空间复杂度：O(1)O(1)O(1)（原地排序）。
稳定性：稳定（相邻交换不破坏相等元素顺序）。
适用场景
适合教学演示或基本有序的小规模数据，实际应用中效率较低。
12.3.2 快速排序
算法原理
核心思想：分治法。选择基准元素，将序列划分为两部分：左部≤基准，右部>基准；递归处理左右两部分，直至子序列长度为1。
划分操作（以第一个元素为基准）：
1.初始化左指针left=0left=0left=0，右指针right=n−1right=n-1right=n−1，基准pivot=arr[left]pivot=arr[left]pivot=arr[left]；
2.右指针左移，找第一个≤pivotpivotpivot的元素，放入leftleftleft位置；
3.左指针右移，找第一个>pivotpivotpivot的元素，放入rightrightright位置；
4.重复步骤2~3，直至left=rightleft=rightleft=right，将pivotpivotpivot放入该位置（基准固定）。
代码实现（原地划分）
python

	def quick_sort(arr, left, right): 
	if left < right: 
	pivot_idx = partition(arr, left, right) # 划分基准位置 
	quick_sort(arr, left, pivot_idx - 1) # 左子序列递归 
	quick_sort(arr, pivot_idx + 1, right) # 右子序列递归 
	
	def partition(arr, left, right): 
	pivot = arr[left] # 基准（第一个元素） 
	while left < right: 
	# 右指针左移找≤pivot的元素 
	while left < right and arr[right] > pivot: 
	right -= 1 
	arr[left] = arr[right] 
	# 左指针右移找>pivot的元素 
	while left < right and arr[left] <= pivot: 
	left += 1 
	arr[right] = arr[left] 
	arr[left] = pivot # 基准放入最终位置 
	return left # 返回基准索引

性能分析
时间复杂度：
o最好情况（基准划分均衡）：O(nlog⁡n)O(nlog n)O(nlogn)（递归深度log⁡nlog nlogn，每层划分O(n)O(n)O(n)）；
o最坏情况（序列有序，基准划分偏斜）：O(n2)O(n^2)O(n2)（递归深度nnn）；
o平均情况：O(nlog⁡n)O(nlog n)O(nlogn)（实际应用中接近最好情况）。
空间复杂度：O(log⁡n)O(log n)O(logn)（递归栈深度，最坏O(n)O(n)O(n)）。
稳定性：不稳定（划分时可能交换相等元素的相对顺序）。
适用场景
适用于大规模数据（平均效率最高，常数因子小），是实际应用中的首选排序算法（需优化基准选择，如随机基准、三数取中法，避免最坏情况）。
12.4 选择排序
12.4.1 直接选择排序
算法原理
核心思想：每次从无序部分选择最小元素，与无序部分的第一个元素交换，使无序部分长度减少1。
步骤：
1.初始无序部分为整个序列（索引0~n-1）；
2.在无序部分中找到最小元素，记其索引为min_idxmin_idxmin_idx；
3.将arr[min_idx]arr[min_idx]arr[min_idx]与无序部分第一个元素交换；
4.缩小无序部分范围（起始索引+1），重复步骤2~3，直至无序部分长度为1。
代码实现
python

	def selection_sort(arr): 
	n = len(arr) 
	for i in range(n - 1): 
	min_idx = i # 无序部分第一个元素索引 
	# 找无序部分最小元素索引 
	for j in range(i + 1, n): 
	if arr[j] < arr[min_idx]: 
	min_idx = j 
	# 交换最小元素与无序部分第一个元素 
	arr[i], arr[min_idx] = arr[min_idx], arr[i] 
	return arr

性能分析
时间复杂度：无论序列是否有序，比较次数固定为∑i=0n−2(n−1−i)=n(n−1)2sum_{i=0}^{{n-2}(n-1-i)=rac{n(n-1)}{2}∑i=0n−2​(n−1−i)=2n(n−1)​，时间复杂度O(n2)O(n}2)O(n2)。
空间复杂度：O(1)O(1)O(1)（原地排序）。
稳定性：不稳定（交换可能破坏相等元素的相对顺序）。
适用场景
适用于数据量小或交换成本低的场景（如链表排序，交换节点指针）。
12.4.2 堆排序
算法原理
核心思想：利用堆（完全二叉树）的特性，通过建堆和调整堆，高效选择最值元素。
堆的定义：大根堆（父节点≥子节点，根节点为最大值）；小根堆（父节点≤子节点，根节点为最小值）。
步骤：
1.建堆：将序列构建为大根堆（根节点为最大值）；
2.交换与调整：将根节点（最大值）与序列末尾元素交换，对剩余元素重新调整为大根堆；
3.重复步骤2，直至堆中仅剩一个元素。
关键操作：堆调整（Heapify）
功能：当节点值小于子节点时，将其“下沉”至正确位置，维持大根堆结构。
python

	def heapify(arr, size, i): 
	"""调整以i为根的子树为大根堆""" 
	max_idx = i # 初始最大值为根节点 
	left = 2 * i + 1 # 左孩子索引 
	right = 2 * i + 2 # 右孩子索引 
	# 找根、左、右中的最大值 
	if left < size and arr[left] > arr[max_idx]: 
	max_idx = left 
	if right < size and arr[right] > arr[max_idx]: 
	max_idx = right 
	# 若最大值非根节点，交换并递归调整 
	if max_idx != i: 
	arr[i], arr[max_idx] = arr[max_idx], arr[i] 
	heapify(arr, size, max_idx)

堆排序实现
python

	def heap_sort(arr): 
	n = len(arr) 
	# 建堆（从最后一个非叶子节点开始调整） 
	for i in range(n // 2 - 1, -1, -1): 
	heapify(arr, n, i) 
	# 交换堆顶与末尾元素，调整堆 
	for i in range(n - 1, 0, -1): 
	arr[0], arr[i] = arr[i], arr[0] # 堆顶（最大）与末尾交换 
	heapify(arr, i, 0) # 调整剩余i个元素为大根堆 
	return arr

性能分析
时间复杂度：
o建堆时间：O(n)O(n)O(n)（堆高度为log⁡nlog nlogn，节点调整时间累加为O(n)O(n)O(n)）；
o调整堆时间：n−1n-1n−1次调整，每次O(log⁡n)O(log n)O(logn)，总时间O(nlog⁡n)O(nlog n)O(nlogn)；
o整体时间复杂度：O(nlog⁡n)O(nlog n)O(nlogn)（最好、最坏、平均均为此）。
空间复杂度：O(1)O(1)O(1)（原地排序，递归调整堆时栈深度O(log⁡n)O(log n)O(logn)，可优化为迭代）。
稳定性：不稳定（交换堆顶与末尾元素可能破坏相等元素顺序）。
适用场景
适用于大规模数据（时间复杂度稳定O(nlog⁡n)O(nlog n)O(nlogn)），但实现较复杂，缓存性能较差（元素访问不连续）。
12.5 归并排序
算法原理
核心思想：分治法。将序列递归分解为两个子序列，直至子序列长度为1（天然有序），再将两个有序子数组合并为一个有序序列。
步骤：
1.分解：将序列从中间分成左右两个子序列，递归分解直至子序列长度为1；
2.合并：将两个有序子数组合并为一个有序序列（类似合并两个有序链表）。
合并操作
python

	def merge(left, right): 
	"""合并两个有序数组left和right""" 
	res = [] 
	i = j = 0 
	# 比较并合并 
	while i < len(left) and j < len(right): 
	if left[i] <= right[j]: 
	res.append(left[i]) 
	i += 1 
	else: 
	res.append(right[j]) 
	j += 1 
	# 合并剩余元素 
	res.extend(left[i:]) 
	res.extend(right[j:]) 
	return res

归并排序实现（递归版）
python

	def merge_sort(arr): 
	if len(arr) <= 1: 
	return arr 
	mid = len(arr) // 2 
	left = merge_sort(arr[:mid]) # 递归分解左子序列 
	right = merge_sort(arr[mid:]) # 递归分解右子序列 
	return merge(left, right) # 合并有序子序列

性能分析
时间复杂度：分解递归深度log⁡nlog nlogn，每层合并时间O(n)O(n)O(n)，总时间O(nlog⁡n)O(nlog n)O(nlogn)（最好、最坏、平均均为此）。
空间复杂度：O(n)O(n)O(n)（需额外数组存储合并结果，递归栈空间O(log⁡n)O(log n)O(logn)）。
稳定性：稳定（合并时相等元素按原顺序放入结果序列）。
适用场景
适用于大规模数据或外排序（如磁盘文件排序，可分块合并），但需额外存储空间。
12.6 排序算法对比与总结
12.6.1 核心指标对比

12.6.2 选择建议
小规模数据：直接插入排序（简单）、冒泡排序（稳定）；
大规模数据：快速排序（平均最快）、堆排序（稳定O(nlog⁡n)O(nlog n)O(nlogn)）、归并排序（稳定，需额外空间）；
基本有序数据：直接插入排序（O(n)O(n)O(n)）、冒泡排序（优化后O(n)O(n)O(n)）；
稳定性要求：归并排序、直接插入排序、冒泡排序；
原地排序要求：除归并排序外均满足。
实际应用中，编程语言内置排序函数（如Python的sorted()）多采用混合策略（小规模用插入排序，大规模用快速/归并排序），兼顾效率与稳定性。

本站原创，转载请注明出处：