8.4 使用二叉树的排序算法*8.5 小结

8.4 使用二叉树的排序算法*

(1) 二叉树排序

有关二叉排序树的代码参见 106 页“10.4 二叉排序树”。
二叉树排序的步骤很简单，就是先把每个元素插入到 BST 中，然后中序遍历。
时间复杂度：O(nlogn)应该清楚地认识到，因为二叉排序树很容易变得不平衡，并且它的空间占用比较大，插入结点也要花费一些时间，所以，二叉树排序比快速排序慢很多。
使二叉排序树不平衡的方法：数据基本有序，BST 退化成长长的链表；或数据使 SBT 形成堆积的“人”字形。

(2) 堆排序

有关堆的代码参见 “10.5 堆和优先队列*”。使用最大值堆，因为这样做可以不占用额外的空间。
堆排序的步骤也不难。操作方法如下：
① 将整个数组转化为一个堆（使用 buildheap 完成）。
② 将堆顶的最大元素取出（removemax），并把它放到数组的最后（准确的说，位置是堆中元素个数减 1）。
③ 剩余元素重新建堆。
④ 重复②，直到堆为空。
时间复杂度：O(nlogn)
堆排序与其他 O(nlogn)的排序算法相比要慢很多。堆排序适用于寻找第 k 大（小）元素。

8.5 小结

搜索算法的比较：
1. 稳定性
插入排序、冒泡排序、二叉树排序、归并排序及其他线性时间排序是稳定的；
选择排序、希尔排序（《资料》里没有总结）、快速排序、堆排序是不稳定的。
2. 时间复杂度
插入排序、冒泡排序、选择排序的时间复杂度为 O(n^2)；
其它非线性时间排序的时间复杂度为 O(nlogn)；
线性时间排序的时间复杂度为 O(n)。
3. 辅助空间
线性时间排序、归并排序的辅助空间为 O(n)，其它排序的辅助空间为 O(1)。
4. 其它方面
插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。在这种情况下，快速排序反而慢了。
当 n 较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。若待排序的记录的关键字在一个明显有限范围内时，且空间允许是用桶排序。
当 n 较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。
当 n 较大时，关键字元素可能出现本身是有序的，对稳定性有要求时，空间允许的情况下，宜用归并排序。
当 n 较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序。