t5
问的是二叉排序树，没问二叉平衡树=.=
t11
稳定的排序算法：
直接插入、冒泡、2归并、基数排序
空间复杂度：
快速排序：借助栈，空间复杂度一般是O(logn)，但在最坏情况下会增长到O(n)
2路归并：因为需要借助辅助空间，所以其空间复杂度一般是O(n)
基数排序：需要借助r个队列，因此其空间复杂度为O(r)
初始时元素：
基本有序：直接插入排序 和 冒泡排序 时间复杂度可以达到O(n)
基本有序或者基本逆序：快速排序 时间复杂度就达到了O(n^2)
每趟排序之后可以确定最终位置：
冒泡 和 堆排 每趟可以确定一个最大值或最小值
快排 每趟也可以确定最终位置（但不一定是一个，要看枢轴划分到哪了）
因为直接插入排序 记录移动次数 一般比 简单选择排序要多，因此当基本本身信息量大，使用简单选择排序
元素基本有序：使用 冒泡 或 直接插入————————时间复杂度都是O(n)
若n较大，一般使用 快排、堆排、归并————————其中快排堆排不稳定，归并稳定；；堆排的空间复杂度为O(1)
n较大，关键字位数可分解，使用基数排序
记录本身信息量很大的时候，可采用链表作为存储结构
注意，若采用链表作为存储结构，那么一般来说，快排、堆排、希尔排序就用不了了
标签：堆排,复杂度,归并,每趟,快排,2020,排序,408 From： https://www.cnblogs.com/basilicata/p/16874859.html