嵌入式 - 数据结构与算法：（1-14）排序算法 - 冒泡/选择/快速/希尔排序对比

上一篇下一篇希尔排序5四种排序算法比较排序算法时间复杂度最好 / 平均 / 最坏空间复杂度稳定性原地排序优点缺点典型使用场景冒泡排序O(n) / O(n²) / O(n²)O(1)稳定是实现极其简单逻辑直观对几乎有序数据效率较高效率低大量冗余交换大数据下性能极差教学演示极小规模数据n 20调试用途选择排序O(n²) / O(n²) / O(n²)O(1)不稳定是交换次数少最多 n−1 次实现简单比较次数固定且多无法利用数据有序性优化内存写入成本高如 Flash的场景教学快速排序O(n log n) / O(n log n) / O(n²)O(log n)平均不稳定是平均性能极佳缓存友好实际应用最快之一最坏情况退化严重如已排序递归可能栈溢出通用高性能排序如 std::sort 底层大数据量内存排序希尔排序O(n log n) / O(n^1.3~1.5) / O(n²)O(1)不稳定是比 O(n²) 算法快很多代码简洁无需递归性能依赖 gap 序列不稳定理论分析复杂中等规模数据n ≈ 1,000~10,000嵌入式系统作为 fallback 排序说明稳定性指相等元素排序后相对位置不变冒泡是唯一稳定的 O(n²) 算法。快速排序最坏情况可通过随机化 pivot 或三数取中避免。希尔排序的平均性能优于冒泡/选择/插入但不如快排、归并。在现代库中如 Cstd::sort、PythonTimsort快速排序或其变种是主力而 O(n²) 算法仅用于极小数组的优化分支。