引言

本章综合前面的简单排序算法+复杂排序算法，给出在不同数据量下的运行时间(单位：ms)。然后对结果进行相关分析，并给出时间复杂度、空间复杂度、稳定性方面的总结。

验证结果

本文选取了不同规模的数据量，另外值得注意的一点是，数据的波动范围应该尽可能的大，若范围过小，则产生相同数据的概率将增大，此时对于像快速排序这样的需要逐个元素判别的算法的效率将大大受到影响。各算法的运行时间如下图所示：

算法	500	5,000	50,000	500,000	500,0000	50,000,000
朴素冒泡排序	8	60	6278	\	\	\
改进冒泡排序	7	57	6043	\	\	\
朴素选择排序	4	22	1474	\	\	\
二元选择排序	4	28	1455	\	\	\
朴素插入排序	2	21	1546	\	\	\
二分插入排序	2	14	477	78455	\	\
二路插入排序	7	328	31831	\	\	\
希尔排序	1	3	11	157	2271	38279
归并排序	0	11	23	104	1022	12507
快速排序	0	4	12	103	1089	16972
堆排序	1	3	13	109	1560	21436
基数排序	0	3	26	102	922	10087

效率分析

• 二路插入排序算法效率整体不高，因为涉及较多取模运算和判定，反而弄巧成拙
• 冒泡排序算法在数据量较小(<5000)时效率还较为可观，但随着数据量增大效率急剧降低
• 选择排序算法和朴素插入排序算法比冒泡排序算法效率高一些，但随着数据量进一步增大效率仍是急剧降低
• 二分插入排序算法相对前面的简单排序算法效果更为可观些，但仍无法应对更大数据量场景
• 希尔排序算法在数据量较小时效果非常可观，基本与复杂排序持平，但随着数据量增大效率仍不及复杂排序
• 论平均效率，在小数据量下 快速排序 = 堆排序 > 基数排序 > 归并排序，但在大数据量下 基数排序 > 归并排序 > 快速排序 > 堆排序。

下面给出这些算法在理论上的时间复杂度、空间复杂度和稳定性：

算法	平均情况	最好情况	最坏情况	空间复杂度	稳定性
冒泡排序	\(O({n^2})\)	\(O(n)\)	\(O({n^2})\)	\(O(1)\)	稳定
选择排序	\(O({n^2})\)	\(O({n^2})\)	\(O({n^2})\)	\(O(1)\)	不稳定
插入排序	\(O({n^2})\)	\(O(n)\)	\(O({n^2})\)	\(O(1)\)	稳定
希尔排序	\(O({n^{1.3}})\)	\(O(n)\)	\(O({n^2})\)	\(O(1)\)	不稳定
归并排序	\(O(n\log n)\)	\(O(n\log n)\)	\(O(n\log n)\)	\(O(n)\)	稳定
快速排序	\(O(n\log n)\)	\(O(n\log n)\)	\(O({n^2})\)	\(O(n\log n)\)	不稳定
堆排序	\(O(n\log n)\)	\(O(n\log n)\)	\(O(n\log n)\)	\(O(1)\)	不稳定
基数排序	\(O(d(r + n))\)	\(O(d(n + rd))\)	\(O(d(r + n))\)	\(O(rd + n)\)	稳定

注：上表基数排序算法中，r表示关键字的基数，d表示长度，n表示关键字的个数。

结语

本文对排序算法进行了对比与效率方面的分析，关于更细节的分析本文并未给出，比如堆排序为什么在大数据量的时候效率并不可观、排序的稳定性受什么因素影响等。另外，本系列文章给出的代码中仍可能有效率不高地方，可以进一步优化。