堆排序算法的时间复杂度为O(nlogn)，一般采用上滤建堆，如果考虑用下滤建堆，不仅可以精简代码，而且时间也会更快。

//堆排序算法的改进
void siftdown(int *v, int l, int u)
{int tmp = v[l], i, c;for(i = l; (c=2*i+1) <= u; i = c ){if(c+1<=u && v[c]<v[c+1])++c;if(tmp < v[c])v[i] = v[c];elsebreak;}v[i] = tmp;   
}void heapsort(int *a, int n)
{for(int i = n/2; i >= 0; --i)siftdown(a, i, n-1);for(int i = n-1; i > 0; --i){int tmp = a[0];a[0] = a[i];a[i] = tmp;siftdown(a, 0, i-1);}
}

时间复杂度分析：（以下分析转载自frank-liu）

结论1：

我们可以发现一个n个元素的树，它的高度相当于logn（向下取整）。

我们再来看我们分析的第二个结论。对应树每一个高度的一层，该有多少个元素呢？假设高度为1的那一层他们的元素个数为k，那么他们的访问时间复杂度为O(k)。根据前面的分析，我们还发现一个情况，就是如果从根结点开始计数，往下第i层的元素如果不是最后一层的话，这一层的元素数量为2**i(2的i次方)。正好这个第i层就相当于树的总高度减去当前层的结点的高度。假设第i层的高度为h，那么也就是i = lgn - h。

结论2：

这一层的元素数量为：

那么他们所有元素的运算时间总和为如下：

根据如下公式：

则有：