05排序操作之桶排序、计数排序、基数排序_桶排序字母计数

桶排序、计数排序、基数排序这三种排序因为时间复杂度都是o(n)线性的，所以这三种排序方法都属于线性排序。这三种算法的原理都不难，时间复杂度和空间复杂度的分析也比较简单，所以我们将讨论的重心放在三种算法各自的适用场景上。

1. 桶排序

桶排序的思想是将待排序的数据分到几个有序的桶里，再将每个桶内的数据自行排序，然后再把每个桶内的数据按顺序取出，得到的序列就是有序的。

1. 时间复杂度分析：如果要排序的数据有 n 个，我们把它们均匀地划分到 m 个桶内，每个桶里就有 k=n/m 个元素，桶排序的时间复杂度最终取决于桶内元素排序方法的选用     （1）桶内部使用归并排序或者快排：每个桶时间复杂度为 O(k * logk)。m 个桶排序的时间复杂度就是 O(m * k * logk)，因为 k=n/m，所以整个桶排序的时间复杂度就是 O(n*log(n/m))。当桶的个数 m 接近数据个数 n 时，log(n/m) 就是一个非常小的常量，这个时候桶排序的时间复杂度接近 O(n)。（2）桶内部使用插入排序（或者冒泡、选择排序）：每个桶时间复杂度为 O(k ^2)。m 个桶排序的时间复杂度就是 O(m * k ^2)，因为 k=n/m，所以整个桶排序的时间复杂度就是 O(n^2/m))。当桶的个数 m 接近数据个数 n 时，n/m 就是常量，这个时候桶排序的时间复杂度也接近 O(n)。
2. 桶排序需要使用额外的桶，其空间复杂度为o(n)
3. 桶排序是否稳定取决于桶内使用的排序算法。

桶排序的使用需要满足：

1. 数据可以很容易划分至m个桶中，并且桶与桶之间有着天然的大小顺序（这样桶内的数据进行排序后，桶与桶之间的数据不需要再进行排序）
2. 数据在各个桶之间分布比较均匀，如果经过划分之后有的桶数据非常多，有的桶数据非常少，那么算法的性能退步就会非常明显，极端情况下，如果所有数据都被分到一个桶中，那么其时间复杂度就会退化为o(nlogn)或者o(n^2)

class Solution{
 
    private static final InsertSort insertSort = new InsertSort();
    public int[] sort(int[]a){
        return bucketSort(a, 5);
    };
 
    public int[] bucketSort(int[]a, int bucketSize){
        if(a.length == 0){
            return a;
        }
        minValue = a[0];
        maxValue = a[0];
        //找到数组中的最小值和最大值
        for(int value:a){
            if(minValue>value){
                minvalue = value;
            }else if(maxValue<value){
                maxValue = value;
            }
        }
        // 生成bucketNum个桶
        int bucketNum = (int)Math.floor((maxValue - minValue)/bucketSize);
        int[][] buckets = new int[bucketNum][0];
 
        //向桶中添加数据
        for(int i=0; i<a.length; i++){
            int index = (int)Math.floor((a[i]-minValue)/bucketSize);
            //buckets是一个二维数组，对应的buckets[i]就是一维数组，arrAppend函数的功能是为一维数组动态扩容
            buckets[index] = arrAppend(buckets[index], a[i]);
        }
        //完成最终的排序
        int arrCount = 0;
        for(int[] bucket: buckets){
            if(bucket.length == 0){
                continue;
            }
            bucket = insertSort.sort(bucket); //插入排序桶内元素
            for(int k=0; k<bucket.length; k++){
                a[arrCount++] = bucket[k];
            }
        }
    
    };
    //实现对数组的动态扩容
    public int[] arrAppend(int[]a, int value){
        int[] arr = Arrays.copyOf(a, a.length+1);
        arr[arr.length-1] = value;         
    }
}

2. 计数排序

计数排序其实是桶排序的一种特殊情况，当待排序的数据范围值不大，如最大值为k时，就可以将所有的值划分到k个桶中，每个桶中的数据都是相同的，这样就省掉了桶内数据排序的时间。

1. 时间复杂度：计数排序的时间复杂度为o(n)
2. 计数排序需要使用额外的temp数组保存数据，故其不是原地排序，其空间复杂度为o(n)
3. 计数排序是稳定的

计数排序的使用需要满足：

1. 计数排序适用于k值不大的时候，如果k的值比数组的长度还大很多，就不适合使用计数排序
2. 计数排序只能给非负整数排序，如果待排序数组存储的是其他类型的数据则需要将数据在不改变其相对大小情况下转换成非负整数。

class Solution{
    public void countSort(int[]a, int n){
        if(n<=0) return;
 
        int maxValue = a[0];
        //遍历找到数组最大值
        for(int value:a){
            if(value > maxValue){
                maxValue = value;
            }
        }
        int[] c = new int[maxValue+1];   //得到各个值的计数数组
        for(int i=0; i<=max; i++){       //为计数数组赋初值
            c[i] = 0;
        }
        for(int value:a){
            c[value] ++;         //得出计数数组每个下标对应的数的个数
        } 
        for(int i=1; i<=max; i++){
            c[i] = c[i] + c[-1];  //将累计个数数组求出来
        }
        
        int[] temp = new int[n];  //生成一个和待排序数组相同大小的数组，用于存储排好序的数组值
        //完成数组的排序过程
        for(int i=n-1; i>0; i--){
            temp[c[a[i]]-1] = a[i];
            c[a[i]]--;
        }
        //将排好序的数组值复制给原数组,整个过程结束
        for(int i=0; i<n; i++){
            a[i]=temp[i];
        }
    }
}

3. 基数排序

基数排序的在实际操作时为了保证算法的稳定性一般是按照位数，从后往前排

1. 基数排序的时间复杂度主要取决于每一位数据排序时使用的线性排序算法的时间复杂度，一把情况下，我们认为，基数排序的时间复杂度近似为o(n)
2. 基数排序时每一位要使用的线性排序都不是原地排序，故基数排序也不是原地排序，其空间复杂度为o(n)
3. 基数排序是稳定的

基数排序使用时需要满足：

1. 需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较了。
2. 每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到 O(n) 了