|
堆排序 堆的定义n个元素的序列{kk…kn)当且仅当满足以下关系时称之为堆 若将和序列{kk…kn)对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树则堆的含义表明完全二叉树中所有非终端结点的值均不大于（或不小于）其左右孩子结点的值由此若序列{kk…kn)是堆则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）这两种堆分别称之为小根堆和大根堆 堆排序（Heap Sort）对一组待排序的关键字首先是把它们按堆的定义排列成一个序列（称为初建堆）这就找到了最大关键字然后将最大的关键字取出用剩下的关键字再重建堆便得到次大关键字如此反复进行直到把全部关键字排好序为止 堆排序算法 堆排序的平均时间复杂度接近于O(nlgn) 堆排序是一种不稳定的排序方法 |
