一亿以上数据几种排序算法运行时间比较
原创
于 2018-10-18 23:13:18 发布
·
1.8k 阅读
·
2
·
5
·
CC 4.0 BY-SA版权
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
文章标签：
#算法
#堆排序
这篇博客对比了一亿以上数据的几种排序算法的运行时间，包括插入排序、堆排序、Shell排序（两种不同增量序列）、快速排序（三取中pivot）以及C库中的qsort方法。实验结果显示，堆排序在大数据量下表现较优。
运行结果如下图（单位ms）
insert：只排了8万及以下数据
heap：参考算法导论，maxHeapify采用迭代取代递归
shell：增量递减序列采用1/2(3k−1)1/2(3^k-1)1/2(3k−1)形式
shell-IS：Incerpi-Sedgewick提出的增量递减序列 [ 1391376, 463792, 198768, 86961, 33936, 13776, 4592, 1968, 861, 336, 112, 48, 21, 7, 3, 1]
hybridquick:pivot为三取中的快排，在递归到少量数据(小于等于16)时采用插入排序直接排序
quick：pivot为三取中的快排
qsort：c库的排序方法，qsort内部实现好像也是采用快排 完整代码如下
#include
#include