十大排序基础排序算法总结与速度对比_十大排序速度

作者：盐析白兔 | 2024-02-25 05:06:24

踩

十大排序速度

测试环境：CPU： i5-3210M 2.5GHz 2.5GHz；内存：4G； Win10 64位系统； VS 2015 release模式 32位。

测试数据均为 int 类型：

取值规则为：(rand() % (N)) * 3 - rand() % (N)

红色字体表示该排序算法仅仅支持非负整数，取值规则为： (rand() % (N)) * 3;

数组大小	1w	10w	100w	1000w	1亿	平均时间复杂度	空间复杂度
未改进的冒泡排序	0.14	15.85	-	-	-	O(n2)	O(1)
改进的冒泡排序 A	0.13	14.66	-	-	-	O(n2)	O(1)
改进的冒泡排序 B	0.13	14.48	-	-	-	O(n2)	O(1)
改进的冒泡排序 C	0.09	10.15	-	-	-	O(n2)	O(1)
选择排序	0.04	3.53	-	-	-	O(n2)	O(1)
直接插入排序	0.02	1.76	-	-	-	O(n2)	O(1)
折半插入排序	0.02	1.77	-	-	-	O(n2)	O(1)
希尔排序	0.001	0.015	0.27	3.54	61.31	O(nlogn)	O(1)
二路快速排序	0.001	0.01	0.09	0.88	9.03	O(nlogn)	O(1)
归并排序递归版本	0.002	0.03	0.29	2.68	28.69	O(nlogn)	O(n)
归并排序递归版本 A	0.001	0.012	0.16	1.44	15.12	O(nlogn)	O(n)
归并排序迭代版本	0.001	0.01	0.14	1.37	14.43	O(nlogn)	O(n)
堆排序递归调整版本	0.001	0.012	0.23	2.76	37.02	O(nlogn)	O(1)
堆排序迭代调整版本	0.001	0.01	0.18	2.45	33.76	O(nlogn)	O(1)
计数排序	-	0.001	0.007	0.058	0.59	O(n+k)	O(k)
桶排序	0.001	0.01	0.13	0.93	9.42	O(n+k)	O(n+k)
基数排序 10为基数	0.001	0.008	0.07	0.7	7.48	O(n·k)	O(n+k)
基数排序 2^k 为基数	-	0.002	0.03	0.2	2.12	O(n·k)	O(n+k)

（* 红色字体表示该排序算法仅仅支持非负整数排序，该数据为非负整数排序的结果）

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/138861

十大排序基础排序算法总结 与 速度对比_十大排序速度