1.分类

1.内部排序和外部排序

• 内部排序：待排序记录存放在计算机随机存储器中（说简单点，就是内存）进行的排序过程。
• 外部排序：待排序记录的数量很大，以致于内存不能一次容纳全部记录，所以在排序过程中需要对外存进行访问的排序过程。

2.比较类排序和非比较排序

• 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
• 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

2.复杂度分析，算法稳定性和适用场景

• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
• 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
• 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
• 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

冒泡：每轮找一个最大值放最后，以此往前递推
选择：每轮找一个最小值放最前，以此往后递推
[1, 8, 5, 2, 6, 9, 3]
[1, 2, 5, 8, 6, 9, 3]
[1, 2, 3, 8, 6, 9, 5]
[1, 2, 3, 5, 6, 9, 8]
[1, 2, 3, 5, 6, 9, 8]
[1, 2, 3, 5, 6, 8, 9]
[1, 2, 3, 5, 6, 8, 9]