(1) 二叉树排序 有关二叉排序树的代码参见106页“10.4 二叉排序树”。 二叉树排序的步骤很简单,就是先把每个元素插入到BST中,然后中序遍历。 时间复杂度:O(nlogn) 应该清楚地认识到,因为二叉排序树很容易变得不平衡,并且它的空间占用比较大,插入结点也要花费一些时间,所以,二叉树排序比快速排序慢很多。 使二叉排序树不平衡的方法:数据基本有序,BST退化成长长的链表;或数据使SBT形成堆积的“人”字形。 (2) 堆排序 有关堆的代码参见108页“10.5 堆和优先队列*”。使用最大值堆,因为这样做可以不占用额外的空间。 堆排序的步骤也不难。操作方法如下: ① 将整个数组转化为一个堆(使用buildheap完成)。 ② 将堆顶的最大元素取出(removemax),并把它放到数组的最后(准确的说,位置是堆中元素个数减1)。 ③ 剩余元素重新建堆。 ④ 重复②,直到堆为空。时间复杂度:O(nlogn) 堆排序与其他O(nlogn)的排序算法相比要慢很多。堆排序适用于寻找第k大(小)元素。
|