我们首先要明晰几点:1,算堆排序的时间复杂度算的是交换次数而不是比较次数。2,设数据个数为N,高度便为lg N。3,为了推算最坏情况,我们用满二叉树,并且N无限大, lg N也无限大
建堆的时间复杂度
为了追求效率,一般选用向下调整建堆。从倒数第二层的最后一个节点开始向下调整,这一层一共有1/4N个节点,最坏情况下每个节点都要向下调整一次,这一层最坏调整1/4N次,倒数第三层有1/8N个节点,最坏情况下每个节点都要向下调整两次,所以倒数第三层最坏要调整1/4N次,倒数第四层有1/16N个节点,最坏情况下每个节点都要向下调整3次,所以倒数第四层最坏情况最坏要调整3/16N次,这三层已经接近3/4N次了,一次往后推,整个向下调整建堆的交换次数接近N次,所以建堆的时间复杂度在O(N)这个量级。
排序的时间复杂度
排序时会让第一个数据和最后一个数据交换,让最后一个数据在第一个数据的位置向下调,直到符合堆的排列规则为止,然后总数减一。最后一层有1/2N个数据,最坏情况下,每个数据都要和第一个数据较换并且向下调整,而下调最坏情况是高度次减一,也就是lg N - 1,因为lg N特别大, lg N ==
lg N - 1。所以最后一层最坏情况是交换1/2N * lg N次,倒数第二层也同理,lg N - 2 == lg N,倒数第三层也同理。所以整体的交换次数是趋近于 N * lg N的,所以排序的时间复杂度在N * lg N这个量级。
堆排序的时间复杂度
把上述的时间复杂度相加的 N + N * lg N == N(1 + lg N),由于lg N 特别大,1可以忽略不计, 所以堆排序的时间复杂度在 N * lg N这个量级。