n = 100000000, 花费时间10270.474ms.
n = 100000000, 花费时间9882.712ms.
n = 100000000, 花费时间10099.3518ms.
n = 100000000, 花费时间10329.1768ms.
n = 100000000, 花费时间10101.7805ms.
n = 100000000, 花费时间33096.636ms.
n = 100000000, 花费时间33492.0657ms.
n = 100000000, 花费时间34915.5091ms.
n = 100000000, 花费时间34353.0611ms.
n = 100000000, 花费时间34147.405ms.
据说是cache的问题。而且堆排序必定调用的\(O(n·logn)\)级别的交换也是问题吧，大概。
交换的次数，平均来算大概是3倍。
快排：
$$ 2^{0} * \frac{n}{4} + 2^{1} * \frac{n}{8} + … $$ $$ = \frac{ n *log_2 n }{4} $$
堆排
$$ \frac{n * log_2 n}{2^{1}} + \frac{n * (log_2 n -1)}{2^{2}} + … $$ $$ = n * log_2 n - ( \frac{1}{2^2}n + \frac{2}{2^3}n + … ) 【log_2 n 个】$$ $$ \geq n*log_2 n - ( \frac{1}{2^2}n + \frac{1}{2^2}n + … ) 【log_2 n 个】$$ $$ = \frac{ 3 * n *log_2 n }{4} $$
来不及验算了，可能有错