排序算法是构建数据结构和算法的基石,它包含内部排序和外部排序两种主要类型。内部排序适用于内存中进行数据排序,而外部排序则用于处理无法一次性加载到内存的大规模数据集。

常见的内部排序算法:

  • 插入排序
  • 希尔排序
  • 选择排序
  • 冒泡排序
  • 归并排序
  • 快速排序
  • 堆排序
  • 基数排序

时间复杂度:

  1. 平方阶 (O(n2)):直接插入排序、直接选择排序、冒泡排序
  2. 线性对数阶 (O(nlog2n)):快速排序、堆排序、归并排序
  3. O(n1+§) (0<§

  4. 线性阶 (O(n)):基数排序、桶排序、箱排序

稳定性:

  • 稳定排序算法:冒泡排序、插入排序、归并排序、基数排序
  • 非稳定排序算法:选择排序、快速排序、希尔排序、堆排序