本文分别介绍桶排序、计数排序和基数排序三种排序算法，这三个算法有着共同的算法思想，下面分别介绍三种排序算法.



桶排序



桶排序(Bucket Sort)的原理很简单，它是将数组分到有限数量的桶子里。



假设待排序的数组a中共有N个整数，并且已知数组a中数据的范围[0, MAX)。在桶排序时，创建容量为MAX的桶数组r，并将桶数组元素都初始化为0；将容量为MAX的桶数组中的每一个单元都看作一个"桶"。在排序时，逐个遍历数组a，将数组a的值，作为"桶数组r"的下标。当a中数据被读取时，就将桶的值加1。例如，读取到数组a[3]=5，则将r[5]的值+1。桶排序过程中存在两个关键环节：



• 元素值域的划分，也就是元素到桶的映射规则。映射规则需要根据待排序集合的元素分布特性进行选择，若规则设计的过于模糊、宽泛，则可能导致待排序集合中所有元素全部映射到一个桶上，则桶排序向比较性质排序算法演变。若映射规则设计的过于具体、严苛，则可能导致待排序集合中每一个元素值映射到一个桶上，则桶排序向计数排序方式演化。

• 排序算法的选择，从待排序集合中元素映射到各个桶上的过程，并不存在元素的比较和交换操作，在对各个桶中元素进行排序时，可以自主选择合适的排序算法，桶排序算法的复杂度和稳定性，都根据选择的排序算法不同而不同。



算法过程



1. 根据待排序集合中最大元素和最小元素的差值范围和映射规则，确定申请的桶个数；

2. 遍历待排序集合，将每一个元素移动到对应的桶中；

3. 对每一个桶中元素进行排序，并移动到已排序集合中。



步骤 3 中提到的已排序集合，和步骤 1、2 中的待排序集合是同一个集合。与计数排序不同，桶排序的步骤 2 完成之后，所有元素都处于桶中，并且对桶中元素排序后，移动元素过程中不再依赖原始集合，所以可以将桶中元素移动回原始集合即可。



演示示例







算法分析



桶排序的时间复杂度为 )，其中 表示桶的个数。由于需要申请额外的空间来保存元素，并申请额外的数组来存储每个桶，所以空间复杂度为 。算法的稳定性取决于对桶中元素排序时选择的排序算法。由桶排序的过程可知，当待排序集合中存在元素值相差较大时，对映射规则的选择是一个挑战，可能导致元素集中分布在某一个桶中或者绝大多数桶是空桶的现象，对算法的时间复杂度或空间复杂度有较大影响，所以同计数排序一样，桶排序适用于元素值分布较为集中的序列。



计数排序



计数(Count sort)排序是桶排序的最为直观的实现，把待排数组元素进行统计，并记录其出现次数，知道每个元素的出现次数，那我们就知道了在某个元素前面到底存在几个元素，即知道了元素在整个数组中的位置，排序完成．下面我们介绍基本的实现步骤．



基本步骤：



1. 申请一个ｋ+1的数组，用来存放排序元素的计数，ｋ可以理解为排序数组中的最大值，遍历整个待排序数组A，将A中每个元素对应C中的元素大小+1

2. 将C中每个i位置的元素大小改成C数组前i项和，这样就知道每个元素具体的位置了；

3. 再申请一个和原数组等长的新数组Ｂ，这样将C中的值恢复到Ｂ中，即完成排序；（恢复到Ａ中也是可以的，这里没有覆盖原数组，新申明了一个）

public static int[] countSort(int[] nums, int k) {
        Arrays.nonBlank(nums);
        int[] c = new int[k + 1];
        int[] b = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            c[nums[i]] += 1;
        }
        for (int i = 0; i < c.length - 1; i++) {
            c[i + 1] = c[i] + c[i + 1];
        }
        for (int i = nums.length - 1; i >=0; i--) {
            b[c[nums[i]] - 1] = nums[i];
            c[nums[i]]--;
        }
        return b;
    }

计数排序时间复杂度为O(n)，这个从上面的实现中，可以分析得出，但是对其时间复杂度影响比较大的还有一个因素就是Ｋ，如果待排数组范围无限大，那么这个ｋ也是无限大的，所需的空间以及遍历的长度就是不可控的，这样算法的线性复杂度也就没有任何意义了。



还有就是在进行浮点数排序时，如果已知浮点数小数点后的范围，即能够预估数据之间等长间隔并记录，这样是可以使用计数排序的，比如都是整数或者0.5结尾的小数（1.5,3.5等）也是可以的，只要将C的数组大小变成2k+2就可以了，否则，计数排序将不能使用。



对于第二个问题，我们来看看算法过程：第一步我们遍历了A数组，因此操作时间是Θ(n)，第二步遍历C数组操作时间是Θ(k)，第三步遍历A数组插入B，因此操作时间是也是Θ(n)。加起来时间复杂度就是Θ(n+k)。据此我们也能得到该算法的适用场景仅限于k较小的情况，如果k很大的话，就不如使用比较排序效率高了。



细心的读者应该发现，最后我们采用倒序遍历，因为前面是顺序遍历，后面采用倒序遍历可以保证数组的稳定性，如果替换成顺序排序则破坏了排序的稳定性，这一点要注意。



基数排序



基数排序(Radix Sort)是桶排序的扩展，它的基本思想是：将整数(或小数)按位数切割成不同的数字，然后按每个位数分别比较，最终排序完成。具体做法是：将待排数组统一为同样的数位长度（这要求预先清楚待排数组的数位范围），数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列．基数排序的具体代码实现如下：

static void count_sort(int a[], int size, int exp) {
    int[] output = new int[size];             // 存储"被排序数据"的临时数组
    int i;
    int[] buckets = new int[10];
    // 将数据出现的次数存储在buckets[]中
    for (i = 0; i < size; i++)
        buckets[(a[i] / exp) % 10]++;
    // 更改buckets[i]。目的是让更改后的buckets[i]的值，是该数据在output[]中的位置。
    for (i = 1; i < 10; i++)
        buckets[i] += buckets[i - 1];
    // 将数据存储到临时数组output[]中
    for (i = size - 1; i >= 0; i--) {
        output[buckets[(a[i] / exp) % 10] - 1] = a[i];
        buckets[(a[i] / exp) % 10]--;
    }
    // 将排序好的数据赋值给a[]
    for (i = 0; i < size; i++)
        a[i] = output[i];
}
/*
     * 基数排序
     *
     * 参数说明：
     *     a -- 数组
     *     size -- 数组长度
     */
static void radix_sort(int a[], int size) {
    int max = get_max(a, size);
    for (int exp = 1; max / exp > 0; exp *= 10)
        count_sort(a, size, exp);
}

基数排序是一种特殊的桶排序，以数位为桶进行划分，通过ｋ次的计数排序来完成最终的数组排序，时间复杂度为O(n)，是稳定排序．



总结



算法这个东西就是每次看同一个算法都会有不同的感受，深入的琢磨一下，就觉得很有意思，但有时候也会被碾压，痛并快着乐，继续往前吧！



对一个人来说，所期望的不是别的，而仅仅是他能全力以赴和献身于一种美好事业。——爱因斯坦