排序算法之计数排序、基数排序、桶排序

一、计数排序

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

当输入的元素是 n 个 0到k之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。

import java.util.Arrays; public class CountingSort { public static void main(String[] args) { int[] arr = {1, 2, 1, 3, 3, 5, 6, 2, 1, 3, 5, 2, 3, 4, 5, 6, 2}; countingSort(arr); System.out.println(Arrays.toString(arr)); } public static void countingSort(int[] arr) { int maxVal = arr[0]; for(int i=0; i<arr.length; ++i) { if(arr[i] > maxVal) maxVal = arr[i]; } int[] temp = new int[maxVal+1]; for(int i=0; i<arr.length; ++i) { temp[arr[i]]++; } int t = 0; for(int i=0; i<temp.length; ++i) { while (temp[i] > 0) { arr[t] = i; temp[i]--; t++; } } } }

二、基数排序

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，每一次关键字的桶分配都需要O(n)的时间复杂度，而且分配之后得到新的关键字序列又需要O(n)的时间复杂度。假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是O(d*2n) ，当然d要远远小于n，因此基本上还是线性级别的。 基数排序的空间复杂度为O(n+k)，其中k为桶的数量。一般来说n>>k，因此额外空间需要大概n个左右。

import java.util.Arrays; public class RadixSort { public static void main(String[] args) { int[] arr = { 58, 3, 542, 748, 14, 214 }; radixSort(arr); System.out.println(Arrays.toString(arr)); } public static void radixSort(int[] arr) { // 遍历得到最大数 int maxVal = arr[0]; for(int i=0; i<arr.length; ++i) { if(arr[i] > maxVal) { maxVal = arr[i]; } } // 最大数是几位数 int maxLen = ("" + maxVal).length(); int[][] bucket = new int[10][arr.length]; int[] bucketElementCounts = new int[10]; // maxLen次遍历分桶 for(int i=0,n=1; i<maxLen; ++i,n *= 10) { for (int j=0; j<arr.length; j++) { // 取出每个元素的个位的值 int digitOfElement = arr[j] / n % 10; bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j]; bucketElementCounts[digitOfElement]++; } // 按照这个桶的顺序（一位数组的下标 取出数据，放入原理的数据） int index = 0; for (int k=0; k<bucketElementCounts.length; k++) { if(bucketElementCounts[k] > 0) { // 循环该桶 即第k个桶 放入 for (int l=0; l<bucketElementCounts[k]; ++l) { arr[index] = bucket[k][l]; index++; } } // 第一轮处理后，要将每个bucketElementCounts[k]置为0； bucketElementCounts[k] = 0; } } } }

三、桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

桶排序最好情况下使用线性时间O(n)，最坏情况为O(n²)，平均为O(n+k)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。