排序算法是构建数据结构和算法的基石,它包含内部排序和外部排序两种主要类型。内部排序适用于内存中进行数据排序,而外部排序则用于处理无法一次性加载到内存的大规模数据集。
常见的内部排序算法:
- 插入排序
- 希尔排序
- 选择排序
- 冒泡排序
- 归并排序
- 快速排序
- 堆排序
- 基数排序
时间复杂度:
- 平方阶 (O(n2)):直接插入排序、直接选择排序、冒泡排序
- 线性对数阶 (O(nlog2n)):快速排序、堆排序、归并排序
- O(n1+§) (0<§
- 线性阶 (O(n)):基数排序、桶排序、箱排序
稳定性:
- 稳定排序算法:冒泡排序、插入排序、归并排序、基数排序
- 非稳定排序算法:选择排序、快速排序、希尔排序、堆排序