前言 　　在高考结束以后，所有人都在等着成绩，政府部门面对几百万的数据，你知道他们是怎么算名次的么？上一次学到递归排序以及快排，确实，用他们可以实现，可是他们的时间复杂度最低都是O（nlogn）。今天我们来看看有没有更快捷的排序方法？ 正文 　　桶排序 　　原理： 将需要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序，排序完成，再将每个桶的数据都取出来，组成新的有序的数据。 　　时间复杂度： 　　排序的数据有n个，分在m个桶里，每一个桶就有k=n/m个元素，每个桶都进行快排，时间复杂度为O（k*lognk），m个桶时间复杂度就为O(m*k*lognk)，因为k=n/m，所以整个桶排序的时间复杂度就O(n*log(n/m))，当桶的个数m接近n时，桶排序的时间复杂度接近O（n） 　　　局限性： 　　　在桶排序的过程中，划分桶时，需要桶和桶之间有着天然的大小顺序，这样桶内元素排序完成以后就不需要在外部排序。 　　　数据在桶之间的分布是较均匀的。划分不均，桶内数据，有些太多，有些太小。时间复杂度就不是常量级的。 　　适用环境： 　　适用于外部排序中，外部排序就是数据存储在外部磁盘中，数据量比较大内存有限，无法将数据全部加载到内存中。假如我们有30G的数据，内存只有8G，怎么办，我们可以使用桶排序的思想，将30G的数据分成6份，每个桶数据都足够在内存中运行，依次排好序然后合并，就都是有序的。 　　计数排序 　　原理：　 例如有8个年龄不同的人，年龄范围为0-5之间，这8个人的考生的成绩，我们放在A[8]数组中，分别为2.5.3.0.2.3.0.3，我们分为6个桶，然后在新的数组B[6]中，遍历A数组，在B中存储对应年龄的个数。然后把数组B[6]数组，顺序求和，变成数组C[6]. B[6]数组: C[6]数组： 后续求解如下图 　　java代码实现： // 计数排序，a 是数组，n 是数组大小。假设数组中存储的都是非负整数。 public void countingSort(int[] a, int n) { if (n <= 1) return; // 查找数组中数据的范围 int max = a[0]; for (int i = 1; i < n; ++i) { if (max < a[i]) { max = a[i]; } } int[] c = new int[max + 1]; // 申请一个计数数组 c，下标大小 [0,max] for (int i = 0; i <= max; ++i) { c[i] = 0; } // 计算每个元素的个数，放入 c 中 for (int i = 0; i < n; ++i) { c[a[i]]++; } // 依次累加 for (int i = 1; i <= max; ++i) { c[i] = c[i-1] + c[i]; } // 临时数组 r，存储排序之后的结果 int[] r = new int[n]; // 计算排序的关键步骤，有点难理解 for (int i = n - 1; i >= 0; --i) { int index = c[a[i]]-1; r[index] = a[i]; c[a[i]]--; } // 将结果拷贝给 a 数组 for (int i = 0; i < n; ++i) { a[i] = r[i]; } } 　　局限： 　　1.计数排序只能用在数据范围不大的场景中，如果数据范围k比要排序的数据n大太多就不适合用计数排序了。 　　2.只能给非负整数排序。所以在给其他数据类型排序时，需要转换为非负整数。 　　解答开题：　　 　　计算排序就像是桶排序的一种特殊排序。当排序数据为n时，所处的范围并不大的时候，比如最大值是k，我们就将数据分为k个桶。这样就剩去了桶内排序； 　　　如何通过成绩高效的排序出名次？ 　　　　解答：我们都知道2018年高考总分为750分，我们可以分成751个桶，对应分数为0到750分，根据考生的成绩，我们将所有的考生都划分带这些桶内，每一个桶的数据都是相同分数的考生，所有桶内的数据不需要进行排序，我们只需要依次扫描每个桶，将桶内的数据输出到一个数组中，就实现了考生排序。 　　基数排序 原理： 　　非比较型整数排序法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。 局限： 　　1.由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以也可以用基数排序算法排序。 　　2.需要可以分割出独立的“位”来比较，而且位之间有递进关系 　　3.每一个“位”的数据范围不能太大，要可以用线性排序算法来排序。否则，时间复杂度就做不到O（n） 字母排序 　　为一串混乱的字符及数字排序，就像sdfHH4IUHIih8uih0HikJ1jHHHu8jyhG7YggUYF,要小写字母排在前面，数字在中间，大写字母在后面，我们又改怎么排序？ 　　解决： 　　利用桶排序思想，弄小写，大写，数字三个桶，遍历一遍，都放进去，然后再从桶中取出来就行了。相当于遍历了两遍，复杂度O(n) 相关文章 数据结构与算法学习笔记之写链表代码的正确姿势（下） 数据结构与算法学习笔记之 提高读取性能的链表（上） 数据结构与算法学习笔记之 从0编号的数组 数据结构与算法学习笔记之后进先出的“桶” 数据结构与算法学习笔记之先进先出的队列 数据结构与算法学习笔记之高效、简洁的编码技巧“递归” 数据结构与算法学习笔记之如何分析一个排序算法？ 数据结构与算法学习笔记之 适合大规模的数据排序 以上内容为个人的学习笔记，仅作为学习交流之用。 欢迎大家关注公众号，不定时干货，只做有价值的输出https://www.cnblogs.com/clwydjgs/p/9878355.html