8. 桶排序
桶排序并不是基于数据比较的，因此比较的高效，时间复杂度接近 O(n)，但是相应地，应用的条件十分苛刻。其思路非常的简单：将要排序的数据分到各个有序的桶内，数据在桶内进行排序，然后按序取出，整个数据就是有序的了。
最好情况下，数据被均匀的分到各个桶中，最坏情况是数据全都被分到一个桶中。
下面是一个桶排序的示例：
public class BucketSort { /** * 测试场景：数组中有10000个数据，范围在(0-100000) * 使用100个桶，每个桶存放的数据范围为：0-999, 1000-1999, 2000-2999，依次类推 */ public static void bucketSort(int[] data){ //新建100个桶 int bucketSize = 100; ArrayList<ArrayList<Integer>> buckets = new ArrayList<>(bucketSize); for (int i = 0; i < bucketSize; i++) { buckets.add(new ArrayList<>()); } //遍历数据，将数据放到桶中 for (int i : data) { buckets.get(i / 1000).add(i); } //在桶内部进行排序 int k = 0; for (int i = 0; i < bucketSize; i++) { ArrayList<Integer> list = buckets.get(i); Integer[] num = list.toArray(new Integer[1]); Arrays.sort(num); //拷贝到data中 for (int n : num) { data[k++] = n; } } } //测试 public static void main(String[] args) { Random random = new Random(); int[] data = new int[10000]; for (int i = 0; i < data.length; i++) { data[i] = random.nextInt(100000); } BucketSort.bucketSort(data); System.out.println(Arrays.toString(data)); } }
9. 计数排序
计数排序其实是一种特殊的桶排序，适用于数据的区间不是很大的情况。
例如给 10 万人按照年龄进行排序，我们知道年龄的区间并不是很大，最小的 0 岁，最大的可以假设为 120 岁，那么我们可以新建 121 个桶，扫描一遍数据，将年龄相同的放到一个桶中，然后按序从桶中将数据取出，这样数据就有序了。
计数排序的基本思路如下：
代码实现：
public class CountingSort { private static void countingSort(int[] data){ int length = data.length; //找到数组的最大值 int max = data[0]; for (int i : data){ if (max < i){ max = i; } } //新建一个计数数组，大小为max+1 //count数组的下标对应data的值，存储的值为对应data值的个数 int[] count = new int[max + 1]; for (int i : data){ count[i] ++; } //根据count数组取出数据 int k = 0; for (int i = 0; i < count.length; i++) { while (count[i] != 0){ data[k ++] = i; count[i] --; } } } }
10. 基数排序
基数排序适用于位数较多的数字或者字符串，思路是将排序的数据按位拆分，每一位单独按照稳定的排序算法进行比较，如下图：
图中的示例，以每个数字为下标，建了 10 个 “桶”，每个桶是一个队列（也可以是数组），然后将要排序的数据按位加入到队列中，然后出队，比较完每一位，则排序完成。
代码实现：
public class RadixSort { private static void radixSort(int[] data) { int maxDigit = maxDigit(data); //新建并初始化10个桶 Queue<Integer>[] queues = new LinkedList[10]; for (int i = 0; i < queues.length; i++) { queues[i] = new LinkedList<>(); } for (int i = 0, mod = 1; i < maxDigit; i ++, mod *= 10) { for (int n : data){ int m = (n / mod) % 10; queues[m].add(n); } int count = 0; for (Queue<Integer> queue : queues) { while (queue.size() > 0) { data[count++] = queue.poll(); } } } } /** * 获取数组最大位数 */ private static int maxDigit(int[] data){ int maxDigit = data[0]; for (int i : data){ if (maxDigit < i){ maxDigit = i; } } return String.valueOf(maxDigit).length(); } }
