使用二叉树的排序算法*

(1) 二叉树排序

有关二叉排序树的代码参见106页“10.4 二叉排序树”。

二叉树排序的步骤很简单，就是先把每个元素插入到BST中，然后中序遍历。

时间复杂度：O(nlogn)

应该清楚地认识到，因为二叉排序树很容易变得不平衡，并且它的空间占用比较大，插入结点也要花费一些时间，所以，二叉树排序比快速排序慢很多。

使二叉排序树不平衡的方法：数据基本有序，BST退化成长长的链表；或数据使SBT形成堆积的“人”字形。

(2) 堆排序

有关堆的代码参见108页“10.5 堆和优先队列*”。使用最大值堆，因为这样做可以不占用额外的空间。

堆排序的步骤也不难。操作方法如下：

① 将整个数组转化为一个堆（使用buildheap完成）。

② 将堆顶的最大元素取出（removemax），并把它放到数组的最后（准确的说，位置是堆中元素个数减1）。

③ 剩余元素重新建堆。

④ 重复②，直到堆为空。时间复杂度：O(nlogn)

堆排序与其他O(nlogn)的排序算法相比要慢很多。堆排序适用于寻找第k大（小）元素。