排序算法全景：从冒泡排序到线性时间排序

摘要排序是算法面试的基本功测试但绝非只是背代码那么简单。本文系统对比 8 种经典排序算法的时间/空间复杂度、稳定性深入讲解快速排序的优化技巧和归并排序的链表版本并展示计数排序、基数排序等线性时间算法。AI 开发者还将学到如何在模型训练中选择合适的排序策略来优化数据流水线。一、排序算法概览1.1 复杂度对比表渲染错误:Mermaid 渲染失败: Parse error on line 3: ... A[冒泡/选择/插入O(n²)] -- B[快排/归并/堆排 -----------------------^ Expecting SQE, DOUBLECIRCLEEND, PE, -), STADIUMEND, SUBROUTINEEND, PIPE, CYLINDEREND, DIAMOND_STOP, TAGEND, TRAPEND, INVTRAPEND, UNICODE_TEXT, TEXT, TAGSTART, got PS图 1排序算法复杂度层次算法平均时间最坏时间空间稳定性适用场景冒泡排序O(n2)O(n^2)O(n2)O(n2)O(n^2)O(n2)O(1)O(1)O(1)✅教学/极小数据选择排序O(n2)O(n^2)O(n2)O(n2)O(n^2)O(n2)O(1)O(1)O(1)❌极小数据插入排序O(n2)O(n^2)O(n2)O(n2)O(n^2)O(n2)O(1)O(1)O(1)✅近乎有序数据归并排序O(nlog⁡n)O(n \log n)O(nlogn)O(nlog⁡n)O(n \log n)O(nlogn)O(n)O(n)O(n)✅链表排序、外部排序快速排序O(nlog⁡n)O(n \log n)O(nlogn)O(n2)O(n^2)O(n2)O(log⁡n)O(\log n)O(logn)❌通用、数组排序堆排序O(nlog⁡n)O(n \log n)O(nlogn)O(nlog⁡n)O(n \log n)O(nlogn)O(1)O(1)O(1)❌内存受限计数排序O(nk)O(n k)O(nk)O(nk)O(n k)O(nk)O(k)O(k)O(k)✅整数、范围小基数排序O(d(nk))O(d(n k))O(d(nk))O(d(nk))O(d(n k))O(d(nk))O(nk)O(n k)O(nk)✅整数、字符串1.2 稳定性的重要性稳定排序相等元素的相对顺序在排序前后保持不变。# 稳定性示例按分数排序后再按年龄排序# 若使用稳定排序相同年龄的人保持分数的有序性students[(Alice,20,90),(Bob,21,85),(Carol,20,85),]# 先按分数排序再按年龄稳定排序# 结果中两个 20 岁的人仍保持分数高低顺序二、核心算法 Python 实现2.1 快速排序面试最常考 排序算法集合 包含快排、归并、堆排及线性时间排序 fromtypingimportListimportrandomclassSortingAlgorithms:排序算法集合staticmethoddefquick_sort(nums:List[int])-List[int]: 快速排序原地版本 核心思想选基准分区递归 时间复杂度平均 O(n log n)最坏 O(n²) 空间复杂度O(log n)递归栈 defpartition(low:int,high:int)-int: 分区操作 选择最后一个元素为基准将数组分为 pivot 和 pivot 两部分 pivotnums[high]ilow-1# i 指向 pivot 区域的最后一个元素forjinrange(low,high):ifnums[j]pivot:i1nums[i],nums[j]nums[j],nums[i]# 将基准放到正确位置nums[i1],nums[high]nums[high],nums[i1]returni1defsort(low:int,high:int)-None:iflowhigh:# 随机选基准避免最坏情况rand_idxrandom.randint(low,high)nums[rand_idx],nums[high]nums[high],nums[rand_idx]pipartition(low,high)sort(low,pi-1)sort(pi1,high)sort(0,len(nums)-1)returnnumsstaticmethoddefmerge_sort(nums:List[int])-List[int]: 归并排序 核心思想分治先排序两半再合并 时间复杂度O(n log n) 空间复杂度O(n) iflen(nums)1:returnnums midlen(nums)//2leftSortingAlgorithms.merge_sort(nums[:mid])rightSortingAlgorithms.merge_sort(nums[mid:])returnSortingAlgorithms._merge(left,right)staticmethoddef_merge(left:List[int],right:List[int])-List[int]:合并两个有序数组result[]ij0whileilen(left)andjlen(right):ifleft[i]right[j]:result.append(left[i])i1else:result.append(right[j])j1result.extend(left[i:])result.extend(right[j:])returnresultstaticmethoddefcounting_sort(nums:List[int])-List[int]: 计数排序 适用于整数、范围已知且不大 时间复杂度O(n k)k 为数值范围 ifnotnums:return[]min_valmin(nums)max_valmax(nums)range_sizemax_val-min_val1# 计数count[0]*range_sizefornuminnums:count[num-min_val]1# 重构有序数组result[]fori,cntinenumerate(count):result.extend([imin_val]*cnt)returnresultdeftest_sorting():测试排序算法print(*60)print(排序算法测试)print(*60)test_cases[[64,34,25,12,22,11,90],[3,-1,0,5,-2],[1],[],[5,5,5,1],]fornumsintest_cases:originalnums[:]quicknums[:]SortingAlgorithms.quick_sort(quick)mergenums[:]mergeSortingAlgorithms.merge_sort(merge)countnums[:]countSortingAlgorithms.counting_sort(count)expectedsorted(nums)status✓ifquickexpectedandmergeexpectedelse✗print(f\n{status}输入:{original})print(f 快排:{quick})print(f 归并:{merge})print(f 计数:{count})if__name____main__:test_sorting()代码 1核心排序算法实现三、AI 场景数据流水线中的排序优化3.1 为什么 AI 需要关注排序场景排序作用推荐算法Dataset 去重排序后相邻去重TimsortPython 内置特征分桶按值排序后分区间计数排序评估指标计算按分数排序计算 AUC归并排序分布式 Shuffle按键排序分发外部归并排序3.2 实际建议最佳实践在 Python 中除非有特定需求否则直接使用sorted()或list.sort()。它们底层是Timsort对真实数据部分有序有极佳性能最坏情况仍是O(nlog⁡n)O(n \log n)O(nlogn)。四、面试高频问题Q1快速排序的最坏情况如何避免答随机选择基准Randomized Pivot三数取中法Median-of-Three尾递归优化减少栈深度。Q2归并排序为什么稳定答合并时当左右子数组元素相等优先取左边元素保持了原相对顺序。Q3什么场景下计数排序比快排快答当数据范围kkk很小如年龄 0-150计数排序的O(nk)O(n k)O(nk)优于快排的O(nlog⁡n)O(n \log n)O(nlogn)。五、总结核心要点快排是面试最常考必须能手写原地版本归并是链表排序首选不需要随机访问稳定性有时很关键多级排序场景线性排序有特定适用域范围有限的整数/字符串。本文基于 Coding Interview University 项目整理专注排序算法专题。