桶排序 桶排序的思想如下： 桶排序思想下的排序都是不基于比较的排序； 时间复杂度为 O(N)，额外空间复杂度为 O(M)； 应用范围有限，需要样本的数据状况满足桶的划分。 这里的桶可以由数组、队列、栈等等来实现，这是一种基于统计的排序算法。 常见的桶排序算法有计数排序和基数排序。 计数排序 计数排序的适用场景要求数据范围不大，且有规律。例如对员工按年龄排序。 通常可以假设员工的年龄是正整数，分布在 [0 ... 100]，我们就建立 100 个桶（Bucket）来统计这些数据。那么在一次 O(N)的遍历中，我们就可…

归并排序 传统的数组排序算法时间复杂度是 O(N^2)，因为每一次扫描数组，只能将 1 个数字移动到目标位置。每一个数的排序过程之间是互不关联的，也就浪费了一些有用的信息。 递归实现 我们用递归的思想来考虑排序问题，如果一个数组分为左右两部分，且两部分别都是有序的，那么我们只需要做一次 O(N)的操作，就可以将整个数组排序。这个操作就是归并排序核心的算法。 然后，为了合并整个大数组，我们先要将这个数组一分为二个部分，然后再继续分为两部分，直到达到最小子问题：当数组中只有一个元素时，他天然就是有序的。 public …