导航菜单

面试专题详解

本页面集合了数据结构与算法面试中的重点专题，包括排序算法、查找算法、图论算法、动态规划以及系统设计。每个专题都包含了基本原理、C++实现、复杂度分析以及典型面试题目。

排序算法全解析

排序算法是算法面试的基础，也是理解算法复杂度与设计思想的良好入口。本专题详细介绍常见排序算法的原理、实现与应用。

排序算法对比

算法平均时间最好时间最坏时间空间复杂度稳定性特点
冒泡排序O(n²)O(n)O(n²)O(1)稳定简单实现适合小数据量
选择排序O(n²)O(n²)O(n²)O(1)不稳定实现简单数据移动少
插入排序O(n²)O(n)O(n²)O(1)稳定适合小规模数据近乎有序效率高
希尔排序O(n^1.3)O(n)O(n²)O(1)不稳定插入排序改进版对中等规模数据高效
归并排序O(n log n)O(n log n)O(n log n)O(n)稳定分治思想外部排序
快速排序O(n log n)O(n log n)O(n²)O(log n)不稳定实际应用最广泛原地排序优化
堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定原地排序求TopK问题
计数排序O(n+k)O(n+k)O(n+k)O(n+k)稳定非比较排序适合范围集中的整数
桶排序O(n+k)O(n)O(n²)O(n+k)稳定非比较排序数据分布均匀时高效
基数排序O(d(n+k))O(d(n+k))O(d(n+k))O(n+k)稳定非比较排序适合字符串或整数