堆排序
堆排序是利用堆这种数据结构而设计的一种排序算法, 堆排序是一种选择排序, 它的最坏, 最好, 平均时间复杂度均为 O(nlogn), 它也是不稳定排序. 首先简单了解下堆结构.
堆
堆是具有以下性质的完全二叉树: 每个结点的值都大于或等于其左右孩子结点的值, 称为大顶堆; 或者每个结点的值都小于或等于其左右孩子结点的值, 称为小顶堆. 如下图:
同时, 我们对堆中的结点按层进行编号, 将这种逻辑结构映射到数组中就是下面这个样子
该数组从逻辑上讲就是一个堆结构, 我们用简单的公式来描述一下堆的定义就是:
大顶堆: arr[i]>= arr[2i+1] && arr[i]>= arr[2i+2]
小顶堆: arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
ok, 了解了这些定义. 接下来, 我们来看看堆排序的基本思想及基本步骤:
来源: http://www.bubuko.com/infodetail-3095081.html