第14章 排序算法
14.1 引言
排序是计算机科学中最基础也最核心的操作之一，其本质是将一组无序数据按特定顺序（如升序、降序）重新排列。在数据库查询、搜索引擎结果排序、数据分析预处理等场景中，高效的排序算法是提升系统性能的关键。
14.1.1 排序算法的评价指标
衡量排序算法性能的核心指标包括：
时间复杂度：算法执行时间与数vb.net教程C#教程python教程SQL教程access 2010教程据规模 n n n 的关系，重点关注比较次数和移动次数；
空间复杂度：算法额外占用的存储空间与 n n n 的关系，分为“原地排序”（O(1) O(1) O(1) 或 O(log n) O(log n) O(log n)）和“非原地排序”（O(n) O(n) O(n)）；
稳定性：若待排序序列中存在相等元素，排序后其相对顺序是否保持不变（如序列 [2,1,2′][2, 1, 2'][2,1,2′]，稳定排序后仍为 [1,2,2′][1, 2, 2'][1,2,2′]，而非稳定排序可能为 [1,2′,2][1, 2', 2][1,2′,2]）；
适用场景：对数据规模、数据分布（如是否接近有序）、数据类型（如整数、字符串）的适应性。
14.1.2 排序算法的分类
根据核心思想和性能特征，本章将排序算法分为三类：
基础排序算法：时间复杂度 O(n2) O(n^2) O(n2)，实现简单，适合小规模数据（如冒泡排序、选择排序、插入排序）；
高级排序算法：基于分治或堆结构，时间复杂度 O(nlog n) O(nlog n) O(nlog n)，适合大规模数据（如归并排序、快速排序、堆排序）；
线性排序算法：非比较排序，时间复杂度 O(n) O(n) O(n)，但依赖数据特性（如计数排序、基数排序、桶排序）。
14.2 基础排序算法
基础排序算法通过简单的比较和交换实现，时间复杂度为 O(n2) O(n^2) O(n2)，但代码简洁，易于理解，是学习排序思想的基础。
14.2.1 冒泡排序（Bubble Sort）

1. 算法原理
   核心思想：重复遍历序列，每次比较相邻元素，若逆序则交换，直至序列有序。因最小（或最大）元素会像“气泡”一样逐渐“上浮”到序列末端，故名冒泡排序。
   步骤：
   1.从序列起始位置开始，依次比较相邻元素 (a[i],a[i+1]) (a[i], a[i+1]) (a[i],a[i+1])；
   2.若 a[i]>a[i+1] a[i] > a[i+1] a[i]>a[i+1]，交换两元素；
   3.遍历至序列末尾后，最大元素已“冒泡”到最后一位，缩小无序区间（不包含已排好的末尾元素）；
   4.重复步骤1~3，直至无序区间长度为1（整个序列有序）。
   优化：若某轮遍历未发生交换，说明序列已有序，可提前结束。
2. 代码实现
   python

	def bubble_sort(arr): 
	n = len(arr) 
	for i in range(n-1): # 无序区间长度从n-1缩小到1（共n-1轮） 
	swapped = False # 标记本轮是否发生交换 
	for j in range(n-1 - i): # 遍历无序区间[0, 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

3. 性能分析
   时间复杂度：
   o最坏情况（逆序序列）：需 n−1 n-1 n−1 轮遍历，每轮比较 n−1−i n-1-i n−1−i 次，总比较次数 ∑i=0n−2(n−1−i)=n(n−1)2 sum_{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(n) O(n) O(n)；
   o平均情况：O(n2) O(n^2) O(n2)。
   空间复杂度：仅需常数级临时变量，O(1) O(1) O(1)（原地排序）。
   稳定性：稳定（仅交换相邻逆序元素，相等元素不交换，相对顺序不变）。
4. 适用场景
   适合小规模数据（n≤1000 n leq 1000 n≤1000）或接近有序的序列，实际应用中较少使用（效率低于插入排序）。
   14.2.2 选择排序（Selection Sort）
5. 算法原理
   核心思想：每轮从无序区间中找到最小（或最大）元素，交换至无序区间的起始位置，直至整个序列有序。
   步骤：
   1.初始无序区间为 [0,n−1][0, n-1][0,n−1]；
   2.在无序区间中找到最小元素，记录其索引 min_idx min_idx min_idx；
   3.交换 a[min_idx] a[min_idx] a[min_idx] 与无序区间起始元素 a[i] a[i] a[i]（i i i 为当前无序区间起始索引）；
   4.缩小无序区间（起始索引 i+1 i+1 i+1），重复步骤2~3，直至无序区间长度为1。
6. 代码实现
   python

	def selection_sort(arr): 
	n = len(arr) 
	for i in range(n-1): # 无序区间起始索引i从0到n-2（共n-1轮） 
	min_idx = i # 记录最小元素索引 
	for j in range(i+1, n): # 遍历无序区间[i+1, n-1] 
	if arr[j] < arr[min_idx]: 
	min_idx = j 
	arr[i], arr[min_idx] = arr[min_idx], arr[i] # 交换最小元素至无序区间起始位置 
	return arr

3. 性能分析
   时间复杂度：无论序列是否有序，每轮需遍历无序区间找最小元素，总比较次数 ∑i=0n−2(n−1−i)=n(n−1)2 sum_{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(n2) O(n^2) O(n2)）。
   空间复杂度：O(1) O(1) O(1)（原地排序）。
   稳定性：不稳定（交换操作可能破坏相等元素相对顺序，如序列 [2,2,1][2, 2, 1][2,2,1]，第一轮交换后变为 [1,2,2][1, 2, 2][1,2,2]，两2的相对顺序未变；但 [3,2,2,1][3, 2, 2, 1][3,2,2,1] 中，第一个2会被交换到索引1，导致相对顺序变化）。
4. 适用场景
   适合数据量小且对稳定性无要求的场景，因交换次数少（仅 n−1 n-1 n−1 次），在硬件资源受限（如嵌入式系统）中可考虑使用。
   14.2.3 插入排序（Insertion Sort）
5. 算法原理
   核心思想：将序列分为“有序区间”和“无序区间”，每次从无序区间取一个元素，插入到有序区间的正确位置，直至无序区间为空。
   步骤：
   1.初始有序区间为 [0,0][0, 0][0,0]（第一个元素），无序区间为 [1,n−1][1, n-1][1,n−1]；
   2.取无序区间第一个元素 x=a[i] x = a[i] x=a[i]（i i i 为无序区间起始索引）；
   3.在有序区间 [0,i−1][0, i-1][0,i−1] 中从后向前遍历，找到 x x x 的插入位置（第一个小于等于 x x x 的元素之后）；
   4.将有序区间中插入位置之后的元素后移一位，插入 x x x；
   5.无序区间起始索引 i+1 i+1 i+1，重复步骤2~4，直至无序区间为空。
6. 代码实现
   python

	def insertion_sort(arr): 
	n = len(arr) 
	for i in range(1, n): # 无序区间起始索引i从1到n-1（共n-1轮） 
	x = arr[i] # 当前待插入元素 
	j = i - 1 # 有序区间末尾索引 
	# 在有序区间中找到插入位置（j+1） 
	while j >= 0 and arr[j] > x: 
	arr[j+1] = arr[j] # 元素后移 
	j -= 1 
	arr[j+1] = x # 插入x 
	return arr

3. 性能分析
   时间复杂度：
   o最好情况（已序序列）：每轮仅需比较1次（无需移动元素），总比较次数 n−1 n-1 n−1，时间复杂度 O(n) O(n) O(n)；
   o最坏情况（逆序序列）：每轮需比较 i i i 次（i i i 为无序区间起始索引），总比较次数 ∑i=1n−1i=n(n−1)2 sum_{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)（原地排序）。
   稳定性：稳定（插入时仅后移大于 x x x 的元素，相等元素不移动，相对顺序不变）。
4. 适用场景
   适合小规模数据或基本有序的序列（如接近已序的日志数据），实际应用中性能优于冒泡和选择排序（如Python的 sorted 函数对小规模数据会切换到插入排序）。
   14.3 高级排序算法
   高级排序算法通过分治策略或堆数据结构，将时间复杂度降至 O(nlog n) O(nlog n) O(nlog n)，是大规模数据排序的首选。
   14.3.1 归并排序（Merge Sort）
5. 算法原理
   核心思想：基于分治策略，将序列递归分解为子序列，排序后合并子序列，直至整个序列有序。
   步骤：
   分解：将序列从中间分为左右两个子序列，递归分解至子序列长度为1（天然有序）；
   合并：将两个有序子序列合并为一个有序序列（核心步骤）。
   合并过程：
   已知有序子序列 left left left 和 right right right，创建临时数组 res res res，双指针遍历 left left left 和 right right right，每次取较小元素放入 res res res，最后将剩余元素追加至 res res res。
6. 代码实现
   python

	def merge_sort(arr): 
	# 递归终止条件：子序列长度为1 
	if len(arr) <= 1: 
	return arr 
	# 分解：中间位置拆分 
	mid = len(arr) // 2 
	left = merge_sort(arr[:mid]) # 左子序列排序 
	right = merge_sort(arr[mid:]) # 右子序列排序 
	# 合并：合并两个有序子序列 
	return merge(left, right) 
	
	def merge(left, right): 
	res = [] # 临时数组存储合并结果 
	i = j = 0 # 双指针遍历left和right 
	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

3. 性能分析
   时间复杂度：
   分解过程：递归深度 log n log n log n（每次分解为2个子序列）；
   合并过程：每层合并总时间 O(n) O(n) O(n)（每个元素参与一次合并）；
   总时间复杂度 O(nlog n) O(nlog n) O(nlog n)（最好、最坏、平均均为 O(nlog n) O(nlog n) O(nlog n)）。
   空间复杂度：递归调用栈深度 O(log n) O(log n) O(log n)，合并需临时数组 O(n) O(n) O(n)，总空间复杂度 O(n) O(n) O(n)（非原地排序）。
   稳定性：稳定（合并时相等元素取左子序列元素，相对顺序不变）。
4. 适用场景
   适合大规模数据（如百万级数组）或要求稳定排序的场景（如电商订单按金额和时间排序），但因非原地排序，空间受限场景需谨慎。
   14.3.2 快速排序（Quick Sort）
5. 算法原理
   核心思想：基于分治策略，选择“基准元素”（pivot），将序列分为“小于基准”“等于基准”“大于基准”三部分，递归排序左右两部分，直至整个序列有序。
   步骤：
   1.选择基准：从序列中选一个元素作为基准（如第一个、最后一个或随机元素）；
   2.分区：将序列分为左（< pivot）、中（= pivot）、右（> pivot）三部分；
   3.递归排序：递归排序左、右两部分，中间部分天然有序；
   4.合并：无需显式合并，左+中+右即为有序序列。
   分区实现（Lomuto 分区方案）：
   选最右元素为基准；
   维护指针 i i i 指向“小于基准区域”的末尾；
   遍历 j j j 从左到右，若 a[j]<pivot a[j] < pivot a[j]<pivot，交换 a[i+1] a[i+1] a[i+1] 与 a[j] a[j] a[j]，i+1 i+1 i+1；
   遍历结束后，交换 a[i+1] a[i+1] a[i+1] 与基准，返回基准位置。
6. 代码实现
   python

	def quick_sort(arr): 
	_quick_sort(arr, 0, len(arr)-1) 
	return arr 
	
	def _quick_sort(arr, low, high): 
	if low < high: 
	# 分区，返回基准位置 
	pivot_idx = partition(arr, low, high) 
	# 递归排序左（[low, pivot_idx-1]）和右（[pivot_idx+1, high]） 
	_quick_sort(arr, low, pivot_idx-1) 
	_quick_sort(arr, pivot_idx+1, high) 
	
	def partition(arr, low, high): 
	pivot = arr[high] # 选最右元素为基准 
	i = low - 1 # 小于基准区域的末尾指针（初始为-1） 
	for j in range(low, high): # 遍历[low, high-1] 
	if arr[j] < pivot: 
	i += 1 
	arr[i], arr[j] = arr[j], arr[i] # 交换到小于区域 
	# 基准放到最终位置（i+1） 
	arr[i+1], arr[high] = arr[high], arr[i+1] 
	return i + 1 # 返回基准位置

优化：
随机基准：避免有序序列导致的最坏情况（如随机选择 [low,high] [low, high] [low,high] 中的元素与最右元素交换）；
三数取中：选左端、中间、右端元素的中位数为基准，优化分区平衡性；
小规模数据切换插入排序：递归到子序列长度小于阈值（如10）时，改用插入排序。
3. 性能分析
时间复杂度：
理想情况（基准每次均分序列）：递归深度 log n log n log n，每层分区时间 O(n) O(n) O(n)，总时间 O(nlog n) O(nlog n) O(nlog n)；
最坏情况（基准为最值，序列有序或逆序）：递归深度 n n n，总时间 O(n2) O(n^2) O(n2)；
平均情况：O(nlog n) O(nlog n) O(nlog n)（随机基准可避免最坏情况）。
空间复杂度：递归调用栈深度 O(log n) O(log n) O(log n)（理想）或 O(n) O(n) O(n)（最坏），原地排序（不考虑递归栈为 O(1) O(1) O(1)）。
稳定性：不稳定（分区交换可能破坏相等元素顺序，如 [2,2,1][2, 2, 1][2,2,1] 选1为基准，交换后变为 [1,2,2][1, 2, 2][1,2,2]，但复杂实现可优化稳定性）。
4. 适用场景
实际应用中最快的排序算法（如C++的 std::sort、Java的 Arrays.sort 底层实现），适合大规模数据（如搜索引擎结果排序），但不稳定且最坏情况性能差，对稳定性和可靠性要求高的场景需用归并排序。
14.3.3 堆排序（Heap Sort）

1. 算法原理
   核心思想：利用堆（完全二叉树）的特性，每次提取堆顶最值元素，调整剩余元素为堆，直至所有元素提取完毕。
   步骤：
   1.建堆：将无序序列构建为大顶堆（升序排序）或小顶堆（降序排序）；
   2.提取最值：交换堆顶（最值）与堆尾元素，缩小堆大小（不包含已提取元素）；
   3.堆调整：将剩余元素重新调整为堆；
   4.重复步骤2~3，直至堆大小为1，序列即有序。
   堆调整（大顶堆）：
   已知节点 i i i 的左右子树为堆，比较 i i i 与左右孩子的最大值；
   若 i i i 不是最大值，交换 i i i 与最大值孩子，递归调整该孩子节点。
2. 代码实现
   python

	def heap_sort(arr): 
	n = len(arr) 
	# 1. 建堆：从最后一个非叶节点开始调整（索引 n//2 - 1） 
	for i in range(n//2 - 1, -1, -1): 
	heapify(arr, n, i) 
	# 2. 提取最值并调整堆 
	for i in range(n-1, 0, -1): 
	arr[0], arr[i] = arr[i], arr[0] # 堆顶（最值）交换到末尾 
	heapify(arr, i, 0) # 调整剩余i个元素为堆 
	return arr 
	
	def heapify(arr, n, i): 
	"""调整以i为根的子树为大顶堆（n为堆大小）""" 
	largest = i # 初始化最大值为根节点 
	left = 2*i + 1 # 左孩子索引 
	right = 2*i + 2 # 右孩子索引 
	# 比较根与左右孩子 
	if left < n and arr[left] > arr[largest]: 
	largest = left 
	if right < n and arr[right] > arr[largest]: 
	largest = right 
	# 若最大值不是根，交换并递归调整 
	if largest != i: 
	arr[i], arr[largest] = arr[largest], arr[i] 
	heapify(arr, n, largest)

3. 性能分析
   时间复杂度：
   建堆时间：O(n) O(n) O(n)（堆的高度为 log n log n log n，每层调整时间和节点数乘积之和）；
   提取最值与调整：共 n−1 n-1 n−1 次，每次调整 O(log n) O(log n) O(log n)，总时间 O(nlog n) O(nlog n) O(nlog n)；
   总时间复杂度：O(nlog n) O(nlog n) O(nlog n)（最好、最坏、平均均为 O(nlog n) O(nlog n) O(nlog n)）。
   空间复杂度：O(1) O(1) O(1)（原地排序，递归调用栈深度 O(log n) O(log n) O(log n)，可优化为迭代实现）。
   稳定性：不稳定（交换堆顶与堆尾可能破坏相等元素顺序，如 [2,2,3][2, 2, 3][2,2,3] 建堆后交换导致顺序变化）。
4. 适用场景
   适合空间受限的大规模数据排序（如嵌入式系统），或需要同时获取最值的场景（如优先级队列），但因缓存不友好（堆节点在内存中不连续），实际性能略低于快速排序。
   14.4 线性排序算法
   线性排序算法不依赖元素比较，通过利用数据的分布特性（如整数范围、位数）实现 O(n) O(n) O(n) 时间复杂度，但有严格的适用条件。
   14.4.1 计数排序（Counting Sort）
5. 算法原理
   核心思想：统计序列中每个整数元素的出现次数，再根据次数计算元素的最终位置。
   步骤：
   1.确定范围：找出序列中的最小值 min_val min_val min_val 和最大值 max_val max_val max_val，计算范围 range=max_val−min_val+1 range = max_val - min_val + 1 range=max_val−min_val+1；
   2.计数：创建计数数组 count count count，统计每个元素出现次数（count[x−min_val] count[x - min_val] count[x−min_val] 为元素 x x x 的次数）；
   3.前缀和：将 count count count 转化为前缀和数组，count[i] count[i] count[i] 表示“小于等于 min_val+i min_val + i min_val+i”的元素个数；
   4.反向填充：从原序列末尾开始，将元素 x x x 放入结果数组的 count[x−min_val]−1 count[x - min_val] - 1 count[x−min_val]−1 位置，count[x−min_val] count[x - min_val] count[x−min_val] 减1（保证稳定性）。
6. 代码实现
   python

	def counting_sort(arr): 
	if not arr: 
	return arr 
	# 步骤1：确定范围 
	min_val = min(arr) 
	max_val = max(arr) 
	range_val = max_val - min_val + 1 
	# 步骤2：计数 
	count = [0] * range_val 
	for x in arr: 
	count[x - min_val] += 1 
	# 步骤3：前缀和（计算元素位置） 
	for i in range(1, range_val): 
	count[i] += count[i-1] 
	# 步骤4：反向填充结果（保证稳定性） 
	res = [0] * len(arr) 
	for x in reversed(arr): 
	idx = count[x - min_val] - 1 
	res[idx] = x 
	count[x - min_val] -= 1 
	return res

3. 性能分析
   时间复杂度：O(n+range) O(n + range) O(n+range)，其中 range range range 为元素值范围。当 range=O(n) range = O(n) range=O(n) 时，总时间 O(n) O(n) O(n)。
   空间复杂度：O(n+range) O(n + range) O(n+range)（计数数组和结果数组）。
   稳定性：稳定（反向填充时相等元素按原顺序放入结果数组）。
4. 适用场景
   适合整数序列且值范围较小的场景（如学生成绩排序，range=100 range = 100 range=100；年龄排序，range=150 range = 150 range=150），不适合浮点数或大范围整数（如身份证号，range range range 过大导致空间爆炸）。
   14.4.2 基数排序（Radix Sort）
5. 算法原理
   核心思想：按元素的“位”（如个位、十位、百位）从低到高依次排序，每轮位排序采用稳定排序（如计数排序），最终实现整体有序。
   步骤：
   1.确定位数：找出序列中最大元素的位数 d d d（如最大元素1234，d=4 d=4 d=4）；
   2.按位排序：从低位（个位）到高位（千位），对每个位进行稳定排序；
   3.经过 d d d 轮排序后，序列即有序。
6. 代码实现
   python

	def radix_sort(arr): 
	if not arr: 
	return arr 
	# 步骤1：确定最大位数 
	max_val = max(arr) 
	d = len(str(max_val)) # 假设arr为非负整数 
	# 步骤2：按位排序（从低位到高位） 
	for i in range(d): # i=0:个位，i=1:十位，... 
	# 计数排序实现位排序 
	count = [0] * 10 # 0~9共10个数字 
	res = [0] * len(arr) 
	# 计数 
	for x in arr: 
	digit = (x // (10 ** i)) % 10 # 提取第i位数字 
	count[digit] += 1 
	# 前缀和 
	for j in range(1, 10): 
	count[j] += count[j-1] 
	# 反向填充（稳定） 
	for x in reversed(arr): 
	digit = (x // (10 ** i)) % 10 
	idx = count[digit] - 1 
	res[idx] = x 
	count[digit] -= 1 
	arr = res # 更新arr为当前位排序结果 
	return arr

3. 性能分析
   时间复杂度：设位数为 d d d，每轮位排序时间 O(n+10) O(n + 10) O(n+10)（计数排序 range=10 range=10 range=10），总时间 O(d(n+10)) O(d(n + 10)) O(d(n+10))。当 d d d 为常数（如整数位数）时，总时间 O(n) O(n) O(n)。
   空间复杂度：O(n+10)=O(n) O(n + 10) = O(n) O(n+10)=O(n)。
   稳定性：稳定（每轮位排序采用稳定排序）。
4. 适用场景
   适合整数、字符串等可按位分解的序列（如电话号码排序、单词字典序排序），但需非负整数或统一正负号，且位数不宜过多（如GUID排序位数太多不适用）。
   14.4.3 桶排序（Bucket Sort）
5. 算法原理
   核心思想：将序列分到多个“桶”中，对每个桶内元素排序（如插入排序），最后合并所有桶。
   步骤：
   1.创建桶：根据数据分布创建 k k k 个空桶；
   2.分桶：将元素按规则放入对应桶（如 bucketidx=int(k∗(x−minval)/(maxval−minval+1)) bucket_idx = int(k * (x - min_val) / (max_val - min_val + 1)) bucketi​dx=int(k∗(x−minv​al)/(maxv​al−minv​al+1))）；
   3.桶内排序：对每个非空桶进行排序；
   4.合并：按桶顺序合并所有桶内元素，即得有序序列。
6. 代码实现
   python

	def bucket_sort(arr): 
	if not arr: 
	return arr 
	# 步骤1：创建桶 
	min_val, max_val = min(arr), max(arr) 
	bucket_count = len(arr) # 桶数通常设为n 
	buckets = [[] for _ in range(bucket_count)] 
	# 步骤2：分桶 
	for x in arr: 
	# 计算桶索引（确保在[0, bucket_count-1]） 
	bucket_idx = int((x - min_val) * (bucket_count - 1) / (max_val - min_val)) 
	buckets[bucket_idx].append(x) 
	# 步骤3：桶内排序（插入排序） 
	for bucket in buckets: 
	insertion_sort(bucket) # 调用14.2.3的插入排序 
	# 步骤4：合并 
	return [x for bucket in buckets for x in bucket]

3. 性能分析
   时间复杂度：假设数据均匀分布，每个桶元素个数 O(n/k) O(n/k) O(n/k)，桶内排序时间 O((n/k)log(n/k)) O((n/k)log(n/k)) O((n/k)log(n/k))，总时间 O(k∗(n/k)log(n/k))=O(nlog(n/k)) O(k*(n/k)log(n/k)) = O(nlog(n/k)) O(k∗(n/k)log(n/k))=O(nlog(n/k))。当 k=O(n) k = O(n) k=O(n) 时，总时间 O(n) O(n) O(n)。
   空间复杂度：O(n+k)=O(n) O(n + k) = O(n) O(n+k)=O(n)（桶和元素存储）。
   稳定性：稳定（桶内用稳定排序，且桶间顺序按规则排列）。
4. 适用场景
   适合均匀分布的浮点数或整数序列（如身高、体重数据排序），但数据分布不均时（如所有元素入一个桶），性能退化为 O(n2) O(n^2) O(n2)，需提前分析数据分布。
   14.5 排序算法性能对比与选择
   14.5.1 性能对比表

14.5.2 算法选择策略
数据规模：
o小规模（n<1000 n < 1000 n<1000）：插入排序（基本有序）或快速排序（随机分布）；
o大规模（n>106 n > 10^6 n>106）：快速排序、归并排序或线性排序（满足条件时）。
数据特性：
o基本有序：插入排序（O(n) O(n) O(n)）；
o整数且范围小：计数排序；
o均匀分布：桶排序；
o可按位分解：基数排序。
空间限制：

空间充足：归并排序、线性排序；
空间紧张：堆排序、快速排序（原地实现）。

稳定性需求：

稳定：归并排序、插入排序、计数/基数/桶排序；
不稳定：快速排序、堆排序、选择排序。
14.6 本章总结
排序算法是数据处理的基础工具，其性能直接影响系统效率。本章从基础、高级到线性排序，系统介绍了9种常用算法，核心结论如下：
基础算法（冒泡、选择、插入）简单但效率低，适合小规模数据，插入排序在基本有序时最优；
高级算法（归并、快速、堆排序）通过分治或堆结构实现 O(nlog n) O(nlog n) O(nlog n) 时间，快速排序实际应用中性能最佳，归并排序稳定但需额外空间，堆排序适合空间受限场景；
线性算法（计数、基数、桶排序）非比较排序，时间 O(n) O(n) O(n)，但依赖数据分布，适合特定场景（如整数范围小、均匀分布）。
选择排序算法时，需综合数据规模、分布、稳定性和空间需求，没有“最优”算法，只有“最适合”的算法。实际应用中，可结合多种算法（如Python的 sorted 函数融合了插入、归并和快速排序的思想），以达到最优性能。
14.7 思考题
1.实现稳定的快速排序（提示：分区时将相等元素分到中间区域）。
2.对比归并排序和快速排序的缓存性能差异（提示：归并排序顺序访问，快速排序随机访问）。
3.如何用计数排序实现浮点数排序（提示：缩放浮点数为整数）？
4.分析堆排序在完全二叉树和满二叉树结构下的性能差异。
5.给定1000万个0~100的随机整数，选择最优排序算法并说明理由。

本站原创，转载请注明出处：https://www.xin3721.com/python3/python49311.html