那些年我们学过的排序算法
在我们校园招聘的时候，大多数的面试官对于一个校招生都可能会问过类似的问题。比如，快排的思路呀，快排的实现呀。当然还有其他的一些经典排序吧！
可能会有很多的同学会想到问这些有什么用吗？因为大多数的时候我们不需要自己写这些排序的呀！
主要问题有两个：
1. 这些你可能都不知道。
2. 不是为了问你具体的实现。
这些东西其实仅仅是为了看一下你是否真的努力学习过了解过。其次，这个东西能不能理解体现着你的理解和学习能力的。如果这些东西你都不知道的话？那么你还怎么去理解更加复杂，更加难懂的业务流程呢？
前面我们说过了这些东西的作用和为什么要知道这些东西。下面我们来说一下这些个算法吧！
首先，我们要对排序算法做一个分类。就按照稳定性来分吧！
不稳定的排序算法有以下几个：
1. 选择排序
2. 快速排序
3. 堆排序
4. 希尔排序
稳定的排序算法：
1. 冒泡排序
2. 插入排序
3. 归并排序
4. 基数排序
什么叫稳定的排序，稳定排序就是排序前后两个相等的数字的相对位置不变化。
时间复杂度，经典排序算法的时间复杂度。
| 算法 | 最优 | 平均 | 最差 | 空间复杂度 | 备注 |
|---|---|---|---|---|---|
| 冒泡排序 | o(n) | o(n2) | o(n2) | o(1) | 这里最优是优化过的排序 |
| 插入排序 | o(n) | o(n2) | o(n2) | o(1) | |
| 希尔排序 | o(n) | o(n1.3) | o(n2) | o(1) | |
| 选择排序 | o(n) | o(n2) | o(n2) | o(1) | |
| 堆排序 | o(n) | o(n*log2*n) | o(n*log2*n) | o(1) | 这里的空间复杂度是在不使用递归的情况下的如果使用递归就和递归深度有关了。 |
| 快速排序 | o(n*log2*n) | o(n*log2*n) | o(n2) | o(log2*n~0（n）) | |
| 基数排序 | o(d(r+n)) | o(d(r+n))) | o(d(r+n)) | o(rd+n) | |
| 归并排序 | o(n*log2*n) | o(n*log2*n) | o(n*log2*n) | o(n) |
具体实现网上代码很多就不给出了。大家尽可以去度娘那里获取答案~~谢谢支持！