lwz blog

# 排序的基本概念

# 排序的定义

排序是将一组无序的记录序列调整为有序的记录序列

# 排序的稳定性

如果一组记录中，存在多个具有相同的关键字，经过排序后，这些记录的相对次序保持不变，则称这种排序算法是稳定的；否则称为不稳定的

例如：有一组记录的关键字为:[(a, 3), (b, 2), (c, 3), (d, 1)]

如果按照关键字升序排序后，得到的结果为:[(d, 1), (b, 2), (a, 3), (c, 3)] a=3,c=3 排序后a始终在c前面，所以是稳定的

如果按照关键字升序排序后，得到的结果为:[(d, 1), (b, 2), (c, 3), (a, 3)]  a=3,c=3 排序后c在a前面，所以是不稳定的

# 内排序与外排序

  • 内排序：待排序的所有记录全部放置在内存中进行排序(关注如何使算法时间、空间复杂度更低)
  • 外排序：待排序的记录的个数很大，不能同时放置在内存中，需要借助外存进行排序(关注如何减少磁盘I/O次数)

# 排序的分类

  • 十大排序算法总结

排序算法复杂度

← 插入排序 →