堆排序时间复杂度计算

1.堆排序

本文举例都是小堆，排降序。

堆排序过程首先需要将 n个 无序的数整理成小（大）堆，其中如果需要排升序则需要建大堆；完成建堆后将堆顶的数（最小的数）交换到最后，将剩下 n-1 个数看成新的堆进行选数。

void heapsort(int* data , int datasize)
{

        assert(data);

        //建大堆
        int i = ((datasize-1-1)/2);
        while (i >=0)

        {
                big_downadjust(data, datasize, i);
                i--;
         }
        printf("建大堆：");
        heapprintf(data, datasize);
        printf("\n");

        //将最大的数放到最后再进行选数
        i = datasize-1;
        while (i > 0)
        {
                exchange( &data[0] ,  &data[i]);
                big_downadjust(data , i , 0);

                i--;
        }
        printf("排序：");
        heapprintf(data, datasize);
        printf("\n");

}

1.1 建堆

建堆有两种方式：向上调整建堆 和 (推荐) 向下调整建堆。

1.1.1 向上调整建堆时间复杂度计算（建小堆）

首先我们要清楚向上调整建堆的时间复杂度计算的是所有节点向上调整次数总合。

以最坏情况建满二叉树计算为例子（设有n层）

1.1.1.1 每层节点个数

每层节点个数是2^（H-1）

1.1.1.2 每个节点所需向上调整次数

当我们想要算出建好一个小堆的时间复杂度时，每个节点所需向上调整的次数也是必须的。

 

1.1.1.3 完成建堆的总向上调整次数

总的时间复杂度 = 每层节点个数 * 每个节点向上调整次数

化简这个公式可以使用高中的错位相减法

化简后为

 

时间复杂度最好和节点个数有关最为直观，所以需要带入高度计算公式：H = log换成和节点个数有关。

出去影响小的项最终结果为：

1.1.1.4 结果向上调整时间复杂度为：O(N*log N)

1.1.2. 向下调整建堆时间复杂度

向下调整建堆的时间复杂度计算与向上调整建堆计算过很相似！这里以建小堆为例：

1.1.2.1 节点个数

1.1.2.2 向下调整总次数计算

所有节点向下调整次数 = 总结点数 + 每个节点向下调整次数

同样使用错位相减法化简

最终获得

继续化简得T(H) = 2^H-1 - H

同样换成和节点个数有关的式子：带入 H = log n+1

除去影响较小得项 最后时间复杂度为n-log n+1 也就是 O(N)

1.1.2.3 时间复杂度为O(N)

1.2 向上建堆和向下建堆对比

向上建堆时间复杂度：O(N*log N)

向下建堆时间复杂度：O（N)

所以选择向下排序建堆原因之一：时间复杂度低 ，之二：建完堆后仍然使用向下调整选数，只用写一个向下调整函数。

1.3 为什么向下建堆比向上建堆快？

向上调整在占节点数一半的最后一层每个节点都要调整 H-1 次；而向下调整最后一层不需要调整且调整次数最多的节点只有堆顶一个数。

1.4 选数时间复杂度计算

//将最大的数放到最后再进行选数
        i = datasize-1;
        while (i > 0)
        {
                exchange( &data[0] ,  &data[i]);
                big_downadjust(data , i , 0);

                i--;
        }
        printf("排序：");
        heapprintf(data, datasize);
        printf("\n");

选数时间复杂度计算只需要理解成向上调整即可！

当每次交换堆顶和堆尾的数后，最后一层的所有节点都需要向上调整 H-1 次，同理第二层需要调整 H-2 次，这与向上调整计算时间复杂度是一致的。所以得出时间复杂度为 O(N*log N)

1.5 堆排序时间复杂度计算

已经算出两种建堆的时间复杂度但我们选择最快的向下调整建堆（ O(N) )，选数时间复杂度为

O( N*log N) 所以堆排序时间复杂度为两个相加得出 O(N*log N).