排序算法概述

排序算法概述

Scroll Down

排序算法概述

1.排序算法的分类

十中常见的排序算法可以分为两大类

  • 非线性时间比较类排序: 通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlon),因此称为非线性时间比较器排序
  • 线性时间非比较类排序: 不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此称为线性时间非比较类排序
    image.png

2.比较

image.png

3.相关概念

  • 稳定:如果a原本在b前面且a=b,排序之后a仍然在b的前面
  • 不稳定:如果a原本在b的前面且a=b,排序后a可能出现在b的后面
  • 内部排序:所有排序操作都在内存中完成
  • 外部排序:待排序记录的数量很大,以至于内存不能容纳全部记录,所以在排序过程中需要对外存进行访问的排序过程