【数据结构与算法】第36篇：排序大总结：稳定性、时间复杂度与适用场景

目录一、十大排序算法总览二、稳定性详解2.1 什么是稳定性2.2 什么时候需要稳定性2.3 各算法稳定性原因三、时间复杂度分析3.1 增长曲线对比3.2 实际运行时间参考n50000随机数据四、空间复杂度分析五、场景选型指南5.1 数据规模小n 10005.2 数据规模中等1000 n 500005.3 数据规模大n 500005.4 特殊场景六、混合排序工业级实现七、面试高频考点7.1 手写代码常考7.2 概念常考八、快速对比卡片O(n²) 级适合小数据O(n log n) 级工业标准O(n) 级特殊场景九、小结十、思考题一、十大排序算法总览算法分类时间复杂度平均时间复杂度最坏时间复杂度最好空间复杂度稳定性冒泡排序交换O(n²)O(n²)O(n)O(1)稳定快速排序交换O(n log n)O(n²)O(n log n)O(log n)不稳定直接插入排序插入O(n²)O(n²)O(n)O(1)稳定希尔排序插入O(n^1.3)O(n²)O(n log n)O(1)不稳定简单选择排序选择O(n²)O(n²)O(n²)O(1)不稳定堆排序选择O(n log n)O(n log n)O(n log n)O(1)不稳定归并排序归并O(n log n)O(n log n)O(n log n)O(n)稳定计数排序非比较O(nk)O(nk)O(nk)O(k)稳定桶排序非比较O(nk)O(n²)O(n)O(nk)稳定基数排序非比较O(d×(nk))O(d×(nk))O(d×(nk))O(nk)稳定k表示数据范围如计数排序中最大值与最小值的差d表示位数基数排序中二、稳定性详解2.1 什么是稳定性稳定排序相等的元素在排序前后相对位置不变。text原数组[(2,A), (1,B), (2,C)] // 数字为键字母为附加信息 稳定排序后[(1,B), (2,A), (2,C)] // 两个2的相对顺序不变 不稳定排序后[(1,B), (2,C), (2,A)] // 顺序可能改变2.2 什么时候需要稳定性场景说明多关键字排序先按A排序再按B排序稳定性能保留A的顺序业务数据排序用户列表按时间排序后再按地区排序同地区内时间顺序不变多次排序后续排序需要保留之前的排序结果2.3 各算法稳定性原因算法稳定性原因冒泡排序稳定相邻交换相等时不交换插入排序稳定相等元素不移动归并排序稳定合并时相等取左边计数/桶/基数排序稳定按顺序分配收集快速排序不稳定分区时可能跨过相等元素希尔排序不稳定分组排序不同组间顺序打乱选择排序不稳定交换可能把后面的相等元素换到前面堆排序不稳定堆化过程无法保证顺序三、时间复杂度分析3.1 增长曲线对比textn1000时各算法大致比较次数 O(n): 1000 O(n log n): 1000 × 10 10000 O(n²): 1000000 n1000000时 O(n): 1000000 O(n log n): 1000000 × 20 20000000 O(n²): 1000000000000无法接受3.2 实际运行时间参考n50000随机数据算法时间(ms)量级快速排序~8最快归并排序~12很快堆排序~15很快希尔排序~20中等基数排序~25中等依赖数据范围冒泡/插入/选择~2000慢注数据因机器而异但相对关系类似四、空间复杂度分析算法额外空间是否原地冒泡/插入/选择/希尔/快排/堆排O(1)是归并排序O(n)否计数排序O(k)否桶排序O(nk)否基数排序O(nk)否内存受限场景优先选择原地排序算法。五、场景选型指南5.1 数据规模小n 1000场景推荐理由基本有序插入排序时间复杂度O(n)无特殊要求插入排序代码简单稳定性好需要稳定冒泡/插入稳定且简单5.2 数据规模中等1000 n 50000场景推荐理由通用场景快速排序平均最快需要稳定归并排序O(n log n)稳定内存紧张堆排序原地O(n log n)数据基本有序插入排序退化为O(n)5.3 数据规模大n 50000场景推荐理由通用场景快速排序常数因子小需要稳定归并排序唯一稳定O(n log n)内存极度紧张堆排序原地排序数据范围小计数/基数排序可达到O(n)5.4 特殊场景场景推荐理由整数且范围小计数排序O(nk)k很小时极快整数且范围大基数排序O(d×n)d通常为常数浮点数/字符串快速排序/归并排序通用比较排序外部排序磁盘归并排序适合多路归并系统级排序混合排序如introsort快排堆排插入六、混合排序工业级实现实际的标准库排序C STLsort、JavaArrays.sort通常采用混合策略数据量大用快速排序递归深度过大切换为堆排序防止最坏情况分区后子数组小用插入排序小数组效率高c// 混合排序伪代码 void hybridSort(int arr[], int left, int right) { if (right - left THRESHOLD) { insertionSort(arr, left, right); return; } if (depth MAX_DEPTH) { heapSort(arr, left, right); return; } int pivot partition(arr, left, right); hybridSort(arr, left, pivot - 1, depth 1); hybridSort(arr, pivot 1, right, depth 1); }七、面试高频考点7.1 手写代码常考算法考察频率快速排序⭐⭐⭐⭐⭐归并排序⭐⭐⭐⭐堆排序⭐⭐⭐⭐插入排序⭐⭐⭐冒泡排序⭐⭐7.2 概念常考稳定性的含义及判断各算法的时间/空间复杂度为什么快速排序实际最快缓存友好、常数因子小堆排序为什么不稳定计数排序的局限性八、快速对比卡片O(n²) 级适合小数据算法一句话记忆冒泡两两交换大的下沉选择每次选最小的放前面插入像打牌插到合适位置O(n log n) 级工业标准算法一句话记忆快速选基准分两边递归归并先分后合需要额外空间堆建堆取堆顶再调整希尔分组插入逐步缩小间隔O(n) 级特殊场景算法一句话记忆计数统计频率直接输出桶分到桶里各桶排序基数按位分配逐位收集九、小结场景首选备选通用排序快速排序归并排序需要稳定归并排序插入排序小数据内存紧张堆排序快速排序整数范围小计数排序基数排序数据基本有序插入排序冒泡排序数据量极小插入排序冒泡排序外部排序归并排序-选型口诀小数据用插入要稳定用归并内存紧用堆排通用场景快排整数范围小计数十、思考题为什么快速排序的实际表现通常优于归并排序即使它们的时间复杂度都是 O(n log n)堆排序是原地排序为什么实际应用中不如快速排序常用计数排序和基数排序的时间复杂度都是 O(n)它们有什么局限性如果你需要排序一个包含100万个整数的文件内存只有50MB应该选择什么算法欢迎在评论区讨论你的答案。