1、十大排序基础排序算法总结 与 速度对比 —— 耗时测试
测试环境：CPU： i5-3210M 2.5GHz 2.5GHz； 内存：4G； Win10 64位系统； VS 2015 release模式 32位。
测试数据均为 int 类型：
取值规则为：(rand() % (N)) * 3 - rand() % (N)
红色字体表示该排序算法仅仅支持非负整数，取值规则为： (rand() % (N)) * 3;
十大基础排序算法 耗时测试（单位：秒）
数组大小 1w10w100w1000w 1亿平均时间复杂度 空间复杂度
未改进的冒泡排序0.1415.85--- O(n2) O(1)改进的冒泡排序 A0.1314.66--- O(n2) O(1)改进的冒泡排序 B0.1314.48--- O(n2) O(1)改进的冒泡排序 C0.0910.15--- O(n2) O(1)选择排序0.043.53--- O(n2) O(1)直接插入排序0.021.76--- O(n2) O(1)折半插入排序0.021.77--- O(n2) O(1)希尔排序0.0010.0150.273.5461.31 O(nlogn) O(1)二路快速排序0.0010.010.090.889.03 O(nlogn) O(1)归并排序 递归版本0.0020.030.292.6828.69 O(nlogn) O(n)归并排序 递归版本 A0.0010.0120.161.4415.12 O(nlogn) O(n)归并排序 迭代版本0.0010.010.141.3714.43 O(nlogn) O(n)堆排序 递归调整版本0.0010.0120.232.7637.02 O(nlogn) O(1)堆排序 迭代调整版本0.0010.010.182.4533.76 O(nlogn) O(1)计数排序-0.0010.0070.0580.59 O(n+k) O(k)桶排序0.0010.010.130.939.42 O(n+k) O(n+k)基数排序 10为基数0.0010.0080.070.77.48 O(n·k) O(n+k)基数排序 2^k 为基数-0.0020.030.22.12 O(n·k) O(n+k)
（* 红色字体表示该排序算法仅仅支持非负整数排序，该数据为非负整数排序的结果）
