# 经典排序算法

十大经典排序算法

算法评定

  • BigO - 大O符号
  • 时间复杂度
    • 对排序数据的总的操作次数,反映当 n 变化时,操作次数呈现什么规律
  • 空间复杂度
    • 指算法在计算机内执行时所需存储空间的度量,它也是数据规模 n 的函数
  • 稳定性
    • 排序后两个相等键值的顺序和排序之前它们的顺序相同

# S. 开始

PS

  • 非线性时间比较类
    • 冒泡,选择,插入,希尔,归并,快速,堆排序
    • 通过比较来决定元素相对次序,其时间复杂度不能突破 O(n log n)
  • 线性时间非比较类
    • 计数,桶,基数排序
    • 不通过比较来决定元素相对次序,可以突破基于比较排序的时间下界,以线性时间运行

# A. 分析

  • n:数据规模
  • k:“桶”的个数
  • In-place:占用常数内存,不占用额外内存
  • Out-place:占用额外内存

图片 图片 图片

时间复杂度

  • 平方阶 (O(n^2)) 排序
    • 冒泡排序,选择排序,插入排序
  • 线性对数阶 (O(n log n)) 排序
    • 归并排序,快速排序,堆排序
  • O(n1 + §)) 排序,§ 是介于 0 和 1 之间的常数
    • 希尔排序
  • 线性阶 (O(n)) 排序
    • 计数排序,桶(箱)排序,基数排序

参考

上次更新时间: 2023-01-16 03:44:08