本文共 1798 字，大约阅读时间需要 5 分钟。

桶排序、计数排序、基数排序

1. 时间复杂度都是 O(n)，不涉及元素之间的比较操作，但对要排序的数据，有特定的适用要求；

2. 桶排序，首先将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序，桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的数据就是有序的；

例子中，n 个数据，分配在 m 个桶中，假设均匀分配，每个桶内有 n/m 个数据	桶内排序，使用快排，时间复杂度是 o((n/m)*log(n/m)),m个桶，总共时间复杂度 o(nlong(n/m))	n 个数据，分配到 m 个桶，时间复杂度是 o(n)	所以总的时间复杂度是 o(n+nlog(n/m)),当n接近于m时，时间复杂度就接近于 o(n)

4. 桶排序适合用在外部排序中，即数据量比较大，内存有限，无法将数据全部加载到内存中；

假设 10GB 的订单数据，需要按订单金额进行排序，内存只有几百兆	假设金额都是正整数，订单金额最小是 1 元，最大是 10 万元	将所有订单根据金额划分到 100 个桶里，依次存放（1,1000）,(1000,2000)...(99000,10000)	每一个桶对应一个文件，如果订单金额比较均匀分布，就被均匀划分到 100 个文件中，对文件进行编号	如此遍历所有数据，写入想要的文件，然后依次读入文件，进行快排，最终写入一个大文件中		如果无法均匀地被划分到 100 个文件中，可能某个金额区间的数据特别多，需要再次划分

5. 计数排序，是桶排序的一种特殊情况，当划分桶时，相同数据特别多，可以按照值不同来划分桶，这样每个桶都是相同数据时，省略了桶内排序时间；

如高考50万考生，按成绩排序，就可以设计0-900个桶，分数相同的放到一个桶中，遍历一次考生数据，就放入所有桶中	然后按顺序从桶中获取数据，就得到按分数排序的考生列表，时间复杂度是 o(n) 	 	首先获取考生最大值，建立一个最大值长度的数组，遍历一遍考生，数组每个元素存放，下标分数的考生数量 	然后对桶数组，依次向后累积，使得数组每个元素 = 小于等于下标分数的考生数，即该分数考生排名的最后一名 	最后遍历一遍考生，考生分数下标的数组元素，即为考生的排名，放入 50 万考生的数组中，并且放入一个元素后，将该下标的		 		桶数组元素-1，这样表示下一个相同分数的考生，应放入的位置

6. 计数排序，只能用在数据范围不大的场，如果数据范围比要排序的数据，大很多就不适合了，而且计数排序只能给正整数排序，其他类型数据，需要不改变相对大小的情况下，转换为非负整数；

7. 基数排序，如果排序数据，可以分割出独立的位，而且位之间有递进关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较了，除此之外，要求每一位的数据范围不能太大，可以用线性排序算法来排序；

假设有 10 万个手机号码，进行排序	快排的时间复杂度是 o(nlogn),计数排序，手机号的范围太大，	我们可以，手机号 11 位，首先按照 第 11 位，进行计数排序，然后按照 第 10 位，进行计数排序，如此类推，直到第 1 位	计数排序是稳定排序，所以最终得到有序集合

8. 要求根据年龄给 100 万用户排序，这就可以用到计数排序，分为 150 个桶；

通用的、高效率的排序函数

1. 如果对小规模数据进行排序，可以选择时间复杂度是 O(n^2) 的算法，如果对大规模数据进行排序，时间复杂度是 O(nlogn) 的算法更加高效，o(n) 的排序算法，要求特定的适用场景；

小规模数据的排序，O(n^2) 的排序算法并不一定比 O(nlogn) 算法执行的时间长

2. 归并排序，空间复杂度 O ( n )，在大规模数据中，不太适用；

3. 快速排序，最坏时间复杂度，可能达到 o(n^2)，快速排序的优化，选择合适的分区点，有三数取中法，随机法，并且要避免递归太深，导致栈溢出；

三数取中，首尾和中间，取三个数，然后从三个数中取一个中间值	更多数据，可能就有五数取中，十数取中

4. 一个比较通用的排序算法，数据量很小可以使用插入排序，数据量小使用归并排序，数据量中等，使用快速排序；

转载地址：http://esfin.baihongyu.com/