请介绍一下你知道的排序算法有哪些
初级答法
常见的排序算法有：冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等
进阶答法
排序算法大致可分为两类：
- A. 基于比较的排序算法
- B. 非比较排序算法
比较排序算法有：快排、归并、堆排序、插入排序等
非比较排序算法有：计数排序、桶排序、基数排序等
比较排序算法中
- 快排、归并、堆排序能够达到 $$O(n \cdot \log{n})$$的（平均）时间复杂度
- 而插入排序的（平均）时间复杂度是 $$O(n^2$$
- 但并不是说复杂度高的算法就差，这要看数据规模和数据有序度，例如
- 数据量小，或是有序度高的数据就适合用插入排序
- 同样是数据量大的数据排序，如果数据的有序度高，归并优于快排
- 快排虽然是比较排序中最快的算法，但若是分区选取不好，反而会让排序效率降低
- 工业级的排序都是混合多种排序算法，例如 java 排序的实现就是混合了插入、归并与快排，不同的数据规模、不同场景下切换不同的排序算法
至于计数、桶、基数可以达到进一步让时间复杂度降至$$O(n$$，当然这与被排序数字的位数、范围等都有关系。
冒泡排序与其它排序算法比较
- 与选择比
- 时间复杂度：都是 O(n^2)
- 交换
- 冒泡在相邻元素两两比较时，遇到逆序元素，立刻就要进行交换
- 选择可以每轮的结束时，把最大元素交换到已排序区
- 选择的交换次数（或者说元素的移动次数）更少
- 稳定性
- 冒泡是稳定排序
- 选择是不稳定排序
- 对有序数组排序
- 冒泡可以优化，时间复杂度能降至O(n)
- 选择不能优化
- 与插入比
- 时间复杂度：都是 O(n^2)
- 交换
- 插入的交换次数更少
- 稳定性
- 二者都是稳定排序算法
- 对有序数组排序
- 都可以只比较一轮，无需交换，时间复杂度达到$$O(n$$
- 与剩余的排序算法比较
- 时间复杂度不在同一级别，无可比性
选择排序与其它排序算法比较
- 同级别像插入、冒泡等都是稳定排序算法，而选择属于不稳定排序算法
- 它们的时间复杂度都一样，平均时间复杂度都是O(n^2)，不咋地
- 选择排序还应当与堆排序比较
- 相似点：都是每轮选出最大元素，交换至已排序区域
- 不同点：数据结构不同，选择排序底层是线性结构，而堆排序结构是大顶堆，这就造成每次选择的效率是堆结构更高
插入排序的适用场景
- 数据规模较小
- 数据有序度高
- 链表排序
插入排序与其它排序算法比较
- 插入排序优于时间复杂度同级的冒泡、选择，它既是稳定排序算法、又能对已排序数据达到$$O(n$$的复杂度
- 插入排序还经常与希尔排序比较，希尔排序可以看作插入排序的增强版
- 工业排序实现中，会结合插入、快排、归并做混合排序
归并排序与其它排序算法比较
常见的是把它与快速排序比较
- 相同点是，二者都基于分治思想，平均时间复杂度都能达到O(n * log{n})
- 分治细节不同
- 归并是分到分无可分、在合并的过程中逐渐有序
- 快排是在每次分区时，就将比基准点小的换到左边分区，比基准点大的换到右边分区，不需要后面合的过程
- 稳定性不同
- 归并是稳定的
- 快排是不稳定的
- 时间复杂度有差异
- 归并，时间复杂度总会保持 O(n * log{n})
- 快排，若基准点选择不好，两个分区划分不均匀，则会退化至 O(n^2)
归并排序能做哪些优化
- 一种常见的优化是，如果切分后的小数组元素较少，可以切换为插入排序，而不必一定要等到元素个数切分至1
- 归并排序通常用递归实现，可以考虑修改为迭代实现，减少递归开销
- 归并排序可以改进为并行归并算法，提升多核 cpu 下的排序能力
快速排序还有哪些优化手段
- 分区不均衡会让快排效率变低。使用随机数作为基准点，避免选中最值基准点导致的分区不均衡
- 如果基准点的重复值较多，则原来算法中的分区效果也不好，要想办法让这些重复值也分布均匀
- 当分区内元素少到一定程度，可以切换为插入排序
堆排序与其它排序算法比较
- 堆排序同级别排序方法有快排、归并等，它们的时间复杂度都是 O(n * log{n})
- 堆排序中的下潜操作涉及到父元素与它的左右孩子交换，数据量较大时，父元素距离它的孩子较远，这样可能会造成（CPU）缓存未命中，增加内存访问成本。快排和归并则没有这个问题
