1. 基于比较的排序算法
时间复杂度$O(n^2)$ 的 排序算法
冒泡排序: 时间复杂度$O(n^2)$，空间复杂度：原地排序，稳定的排序算法。
快速排序: 时间复杂度$O(n^2)$，空间复杂度：原地排序，稳定的排序算法。
选择排序: 时间复杂度$O(n^2)$，空间复杂度：原地排序，不稳定的排序算法。
上述三种排序算法因为时间复杂度比较高，$O(n^2)$。因此只适合小规模数据的排序。
时间复杂度$O(nlogn)$的排序算法
对于大规模数据进行排序，应该选择时间复杂度$O(nlogn)$的排序算法。
归并排序: 时间复杂度$O(nlogn)$，空间复杂度On, 稳定的排序算法。算法思想用到了分治思想。
缺点：实战中使用归并并不多，这是因为归并不是原地排序算法。粗略举例来说，100MB数据，除了数据本身占用的内存之外，排序算法那还需要额外占用100MB的内存，空间耗费翻倍。
快速排序: 时间复杂度 $O(nlogn)$，原地排序，不稳定的排序算法。
谈谈快排的优化，快排可能导致性能差的几点：
快排性能脆弱点1：分区哨兵点选择，哨兵点选择不对可能时间复杂度退化为$O(n^2)$。 快速排序性能关键点在于 pivot分区哨兵点选择。如果数据原来就是有序，每次pivot分区哨兵点都选择最后一个数据，那么快排时间复杂度退化为$O(n^2)$。 最理想的分区点是：被分区点分开的两个分区中，数据的数量差不多。常用的分区点选择算法：
- 三数取中法。从区间的首、尾、中间分别取一个数，然后对比大小，取这三个数的中间值作为分区点。
- 随机法。随机选择一个元素作为分区点，从概率的角度来看这种要好一些。
快排性能脆弱点2：快排依赖了递归，警惕堆栈溢出。解决办法：
- 限制递归深度，一旦超过设定的阈值，就停止递归；
- 在堆上模拟实现一个函数调用栈，手动模拟递归压栈、出栈的过程，这样就没有了系统栈大小的现在。
堆排序
2. 非基于比较排序
时间复杂度$O(n)$
桶排序
计数排序
基数排序