。

它是通过堆#xff08;若不清楚什么是堆#xff0c;可以看我前面的文章#xff0c;有详细阐述#xff09;来进行选择数据堆这种数据结构所设计的一种排序算法它是选择排序的一种。

它是通过堆若不清楚什么是堆可以看我前面的文章有详细阐述来进行选择数据通过向下调整算法从第一个非叶子结点开始在局部先创建出大堆或小堆然后父亲结点不断往上走直到整棵树都建成一个堆。

然后不断交换根节点和最后一个节点的值交换完后节点的数目减1因为最后一个节点已经是它应该在的位置了不用再参与建堆再从根节点向下建堆除最后一个节点其它节点又会建成一个堆

实现堆排序最重要的就是实现向下调整算法。

以下是向下调整算法的代码以及解释

void

a[child]判断左右孩子的大小取左右孩子中大的那一个child;if

(a[child]

a[root])//入过孩子的值比父亲的值大就交换孩子和父亲的位置Swap(a[child],

a[root]);else//如果孩子的值不比父亲的值大就证明大堆已经建好了因为此时父亲的左右子树都是大堆//直接break跳出循环。

break;//没有break来到这里就顺着子树继续往下走root

child;child

2找到第一个非叶子节点从第一个非叶子结点开始向下建堆AdjustDown(a,

end

0){//假设是建大堆将下标为0的元素和下标为end的元素交换//最大的数就排到最后了也就相当于最后的那个数已经排好了不用再参与下面的向下建堆Swap(a[0],

end,

0);//还没有排好的数向下建堆从0位置开始向下建堆end--;}

四、总结

向下建堆时间复杂度为O(N)排序时间复杂度为O(N*logN)

空间复杂度O(1)