堆排序的时间复杂度分析_堆排序的间复杂度证明

关于初始化堆：

因为初始化堆，是每个数据向下冒泡，每一层冒泡的次数不同，最高层冒泡的次数最多为logn,最底层为1次，设共有h层（h=logn) , 时间复杂度的计算为：1*h+2*(h-1)+4*(h-2)+...+2^(h-1)*1

即【节点数*所在层数】的累加，如2*（h-1）即第二层有两个节点，因为在第二层，所以会冒泡h-1次

可以转化为通项： 

k从0到h-1的累加 用错项相减法求 可以得到O()，即O（）即O（n)

关于调整堆/删除堆：

因为在调整的时候，每调整/删除一次，树的节点就会少一个（跑到有序堆去了），然鹅每次调整的时候，是从下往上冒泡的，所以调整的次数即当前树的层数，那怎么确定当前树的层数呢，直接对当前节点取对数就好了，每一个节点都要进行这样的操作，所以操作的次数是log(n-1)+log(n-2)+...+log2+log1=log(n-1)!=nlogn这个的证明我看了下面这个大佬的链接：）

log(n!) = Θ(n·log(n))_piaopiaolanghua的博客-CSDN博客_log(n!)

故时间复杂度为O（nlogn)

故整个堆排序 时间复杂度取大的O（nlogn)