一、10算法分类
本文一共总结了10种排序算法，其中
基于比较的排序算法有
冒泡排序，插入排序，希尔排序，选择排序，归并排序，堆排序，快速排序；
线性时间排序算法包括
计数排序，基数排序，桶排序；
前边有提到过，基于比较的排序算法，时间复杂度最差达到O(nlogn)O(nlogn)，无法突破这个界限，只有线性时间排序能够突破，达到O(n)O(n)，所以说，如果满足了线性时间排序算法的限制条件，使用线性时间排序将会使排序性能得到极大提升。
二、实际测试数据
下面对以上涉及到的每种算法做一个简单的实际测试对比：利用随机数，随机生成区间0 ~ K之间的序列，共计N个数字，利用各种算法进行排序，记录排序所需时间，测试环境为i7+vs2015+Debug版本。
算法\输入数据N=50 K=50N=200 K=100N=500 K=500N=2000 K=2000N=5000 K=8000N=10000 K=20000N=20000 K=20000N=20000 K=200000
冒泡排序
0ms
15ms
89ms
1493ms
9363ms
36951ms
147817ms
143457ms
插入排序
1ms
13ms
82ms
1402ms
8698ms
34731ms
134817ms
134836ms
希尔排序
0ms
1ms
6ms
30ms
110ms
257ms
599ms
606ms
选择排序
0ms
5ms
31ms
461ms
2888ms
11736ms
45308ms
44838ms
堆排序
0ms
3ms
9ms
40ms
124ms
247ms
525ms
527ms
归并排序
2ms
6ms
18ms
75ms
199ms
392ms
778ms
793ms
快速排序
0ms
1ms
2ms
14ms
36ms
84ms
196ms
163ms
计数排序
0ms
1ms
1ms
5ms
15ms
32ms
51ms
62ms
基数排序
0ms
1ms
4ms
19ms
47ms
114ms
237ms
226ms
桶排序
0ms
2ms
6ms
25ms
68ms
126ms
254ms
251ms
三、性能对比小结
1. 传统简单排序确实当数据量很小的时候也表现不错，但当数据量增大，其耗时也增大十分明显；
2. 冒泡，插入，选择三种排序中，当数据量很大时，选择排序性能会更好；
3. 堆排，希尔，归并，快排几种排序算法也表现不错，源于其时间复杂度达到了O(nlogn)O(nlogn)；
4. 随机快速排序性能确实表现十分亮眼，甚至有时比基数排序和桶排序还好，这可能也是快排如此流行的原因；
5. 线性排序中计数排序表现最好，但他们的限制也比较明显，只能处理范围内的正整数。