排序算法
排序是最基本的算法之一。
十大经典排序算法
- 插入排序
- 冒泡排序
- 选择排序
- 希尔排序
- 计数排序
- 基数排序
- 快速排序
- 归并排序
- 桶排序
- 堆排序
关于时间复杂度
计算方式
- 时间（空间）复杂度的计算公式：( T(n) = O(f(n)) )
- ( T(n) )：代码执行的时间
- ( f(n) )：每一行代码执行次数的总和（通常只关注量级最大的项，忽略低阶、常数和系数）
- 若 ( f(n) = 2n^2 + 2n + 3 )，则 ( T(n) = O(n^2) )
- ( n )：数据规模
常见复杂度量级
- 常数阶：( O(1) )
- 执行时间不随数据规模变化
- 对数阶：( O(\log n) )
- 搜索空间每次缩小一半，关键操作次数约 ( \log_2 n )
- 线性阶：( O(n) )
- 执行时间与数据规模成正比
- 线性对数阶：( O(n \log n) )
- k次方阶：( O(n^k) )
- 指数阶：( O(2^n) )
- 阶乘阶：( O(n!) )
桶排序
桶排序是一种将待排序数据分配到多个"桶"中，对每个桶单独排序，最后合并结果的算法。
适用场景：数据分布均匀且范围有限的情况。
算法步骤
- 确定桶的数量和大小
- 根据数据范围和分布设定桶（如数据范围0~100，可设10个桶，每个桶负责10个数据）。
- 分配数据到桶
- 遍历数据，将每个元素放入对应的桶。
- 桶内排序
- 对每个桶中的元素排序（可使用任意排序算法）。
- 合并结果
- 将所有桶的有序数据按顺序合并。
快速排序
快速排序是一种分治算法，通过递归划分数组实现排序。
算法步骤
- 选择基准元素（pivot）
- 从数组中任选一元素（通常选首元素、尾元素或中间元素）。
- 分区（Partitioning）
- 重排数组：
- 所有小于基准的元素移到基准左侧。
- 所有大于基准的元素移到基准右侧。
- 重排数组：
- 递归排序
- 对左侧子数组和右侧子数组递归执行快速排序。
- 合并结果
- 由于是原地排序，无需额外合并步骤。
示例过程
初始数组：
[ 10, , 3, , 5, , 7, , 1, , 6, , 4, , 2, , 8, , 9 ]
分区操作：
- 基准选10 → 分区后：[ 3, \, 5, \, 7, \, 1, \, 6, \, 4, \, 2, \, 8, \, 9, \, \textcolor{red}{10} ]
- 左侧子数组递归（基准选3）：[ 1, \, 2, \, \textcolor{red}{3}, \, 5, \, 7, \, 6, \, 4, \, 8, \, 9 ]
- 右侧子数组递归（基准选5）：[ 4, \, \textcolor{red}{5}, \, 7, \, 6, \, 8, \, 9 ]
- 最终有序数组：
[ 1, , 2, , 3, , 4, , 5, , 6, , 7, , 8, , 9, , 10 ]
作业
封装一个数据结构库（DatastructureLibrarys），包含以下内容：
- 基础数据结构：
- 链表
- 栈
- 队列
- 优先队列
- 二叉树（二叉排序树/平衡二叉树）
- 图
- 排序算法：
- 实现十大经典排序算法（如桶排序、快速排序等）。
总结：
- 桶排序：适合均匀分布数据，分桶后排序合并。
- 快速排序：高效分治策略，平均复杂度 ( O(n \log n) )。
- 时间复杂度：是算法性能的核心指标，需根据场景选择合适的排序算法。