1.3 排序算法的评估指标

评估一个排序算法,需要综合考虑以下指标:

  • 时间复杂度:包括最好情况、最坏情况和平均情况的时间复杂度
  • 空间复杂度:算法运行所需的额外内存空间
  • 稳定性:相等元素的相对顺序在排序后是否保持不变
  • 适应性:算法是否能够利用输入数据已有的部分有序性
  • 原地性:是否只需要常数级别的额外空间
  • 比较次数与交换次数:对于基于比较的排序,这两者直接影响实际运行效率
  • 缓存友好性:算法对 CPU 缓存的利用效率