No.1.4 排序 - 小结

一、时间复杂度：

　　1.毫无疑问，桶排序是最快的，时间复杂度为 O(N+M)，N=初始化列表长度，M=输入队列的长度

　　2.冒泡排序是最慢的，时间复杂度 O(N*(N-1)/2) ~~ O(N**2)

　　3.快速排序是对冒泡排序的一种改进，时间复杂度为 O(NlogN)

　　比如说，当今计算机的计算能力达到每秒10亿次（实际要更快），对于一个N=10000，M=1000的排序问题，各自的解出时间：

　　桶排序：(10000 + 1000) / 10亿 = 1.1 微妙

　　冒泡排序：1000*1000 / 10亿 = 1 毫秒

　　快速排序：1000 * log1000 ~= 10 微妙

二、列表长度

　　1.桶排序的最大问题是，浪费空间，有多少种类就要初始化多长的列表，但是计算机的内存是有限的，以 32bytes为例，超出-2147483648~2147483647 的话，就不能使用桶排序；

　　2.冒泡排序的最大问题是，太慢（当然，如果N不大的话，也没什么问题），对于时效性要求高的问题，不适合用；

　　3.快速排序算法，就介于桶排序和冒泡排序之间，很多时候，最适合的算法不一定是最快的，但一定是最优的！