排序算法 - 简介

一、分类

• 比较排序

  1. 通过比较决定元素次序
  2. 时间复杂度无法突破 O($n \log n$)

• 非比较排序

  1. 不通过比较决定元素次序
  2. 可以突破比较排序的时间下限

二、复杂度

• 稳定性：两个相等的元素在经过排序后的先后次序不变，则称这个排序算法稳定
• 时间复杂度：反应排序算法的总操作次数与数据规模 $n$ 之间的关系
• 空间复杂度：反应排序算法在执行过程中所需的存储空间与数据规模 $n$ 之间的关系