1、堆

堆结构

堆结构就是用数组实现的完全二叉树，完全二叉树中如果每颗子树的最大值都在顶部就是大根堆，完全二叉树中如果每颗子树的最小值都在顶部就是小根堆，优先级队列结构也是堆结构。

堆排序

先让整个数组都变成大根堆结构，建立堆的过程：
1、从上到下的方法，时间复杂度O(N*logN)
2、从下到上的方法，时间复杂度O(N)
把堆的最大值和堆末尾的值交换，然后减少堆的大小之后，再去调整堆，一直周而复始，时间复杂度O(N*logN)，堆的大小减成0之后，堆排序结束。

已知一个几乎有序的数组，请选择一个合适的排序策略，对这个数组进行排序。（☆几乎有序：如果把数组排好序的话，每个元素移动的距离一定不超过k，并且k相对于数组长度来说是比较小的）

自定义堆比较器

2、前缀树

单个字符串中，字符从前到后的加到一颗多叉树上。字符放在路上，节点上有专属的数据项（常见的是pass和end），所有样本都这样添加，如果没有路就新建，有路就复用，沿途节点的pass值增加1，每个字符串结束时来到的节点end值增加1，一般可用于完成前缀相关的查询。

前缀树-支持英文以外的字符

3、桶排序-计数排序&基数排序

桶排序思想下的排序都是不基于比较的排序，时间复杂度为O(N)，额外空间复杂度为O(M)，应用范围非常有限，需要样本的数据状况满足桶的划分。

计数排序

基数排序

4、排序算法的稳定性

稳定性是指同样大小的样本在排序之后不会改变相对次序，对基础类型来说，稳定性毫无意义；对非基础类型来说，稳定性才有意义。有些排序算法可以实现成稳定的，而有些排序算法无论如何都实现不成稳定的。

不基于比较的排序，对样本数据有严格要求，不易改写；

基于比较的排序，只要规定好两个样本怎么比大小就可以直接复用；

基于比较的排序，时间复杂度的极限是O(N*logN)

时间复杂度O(N*logN)、额外空间复杂度低于O(N)、且稳定的基于比较的排序不存在；

为了绝对的速度选快排，为了省空间选堆排，为了稳定性选归并。

常见的坑：

① 归并排序的额外空间复杂度可以变成O(1)，“归并排序内部缓存法”，但是将变得不在稳定；

② “原地归并排序”垃圾，会让时间复杂度变成O(N^2)；

③ 快速排序稳定性改进，“01 stable sort”，但是对样本数据要求更多；

④ 在整型数组中，请把奇数放在数组左边，偶数放在数组右边，要求所有奇数之间原始的想对次序不变，所有偶数之间原始相对次序不变，且要求时间复杂度做到O(N)，往外空间复杂度做到O(1)，抱歉这做不到；因为奇、偶的要求是一个“零一标准”（不是奇数就是偶数），在快速排序中的partition是做不到稳定性的，如果能做到稳定性的话，快速排序为什么不改成稳定的呢？

工程上对排序的改进：

① 出于对稳定性的考虑；

② 充分利用O(N*logN)和O(N^2)排序各自的优势。