排序基础之非比较的计数排序、桶排序、基数排序(Java实现)

public class CountingSort {
    public int[] countingSort(int[] A, int n) {
        if(A==null||A.length<=0){
            return A;
        }
        
        //找出待排序数组最大值
        int Max=A[0];
        for(int i=1;i<n;++i){
            Max=(Max>A[i])?Max:A[i];
        }
        
        //由待排数据最大值，创建辅助数组
        int[] count=new int[Max+1];
        
        //计数
        for(int i=0;i<n;++i){
            count[A[i]]++;
        }
        
        //计算出值i在结果数组中的位置（第k位）
        for(int i=1;i<Max+1;++i){
            count[i]=count[i-1]+count[i];
        }
        
        
        int[] res=new int[n];
        int val;
        int pos;
        
        
        for(int i=0;i<n;++i){
            val=A[i];
            
            //count[val]为val值在结果数组中的第count[val]位，由于数组下标从0开始，那么对应的下标就是count[val]-1
            pos=count[val]-1;
            //把val填到结果数组中自己的位置上
            res[pos]=val;
           
            //值为val的数已经排好了一个，那么小于等于val的值就要减少一个了
            count[val]=count[val]-1;
        }
        
        return res;
    }
}

public class RadixSort {
    public int[] radixSort(int[] A, int n) {
        if(A==null||A.length<=0){
            return A;
        }
        
        //求最大值最小值
        int Max=Integer.MIN_VALUE;
        int Min=Integer.MAX_VALUE;        
        for(int i:A){
            if(i<Min){
                Min=i;
            }
            if(i>Max){
                Max=i;
            }
        }
        
        //得到区间
        int range=Max-Min;
        //得到桶总数
        int total=range/n+1;
        
        //创建桶数组，由于每个桶是动态添加数据的，所以使用ArrayList
        ArrayList<ArrayList<Integer>> buckets=new ArrayList<ArrayList<Integer>>(total);
        for(int i=0;i<total;++i){
            buckets.add(new ArrayList<Integer>());
        }
        
        //遍历待排数组，计算出A[i]所处区间，然后入桶
        int pos;
        for(int i=0;i<n;++i){
            pos=A[i]/range;
            buckets.get(pos).add(A[i]);
        }
        
        //对每个桶内数据进行小范围排序
        for(ArrayList arr:buckets){
            Collections.sort(arr);
        }
        
        //从排序后桶数组中依次取出数据，即为排序后结果
        int[] res=new int[n];
        int index=0;
        for(ArrayList arr:buckets){
            for(Object i:arr){
                res[index]=(int)i;
                index++;
            }
        }
        
        return res;
    }
}

public class RadixSort {
    public int[] radixSort(int[] A, int n) {
        if(A==null||A.length<=0){
            return A;
        }
        //找出待排数组最大值，得到待排数据最高位
        Integer Max=Integer.MIN_VALUE;        
        for(int i:A){
            if(i>Max){
                Max=i;
            }
        }

int maxindex=(Max.toString().length());
        
        //创建一个临时数组，存放从低位到高位排序期间的临时结果
        int[] temp=new int[n];
        
        //计数排序所用的计数数组
        int[] buckets=new int[10];
        
        int rate=1;//从低位开始，倍数为1.后面为10，100...用于计算排序位是哪位
        
        //从低位到高位，根据排序位值排序
        for(int index=1;index<=maxindex;++index)
        {
            //把上一次排序位排序后的A数组，赋值到临时数组中
            System.arraycopy(A,0,temp,0,n);
            //重置计数排序数组
            Arrays.fill(buckets, 0); 
            
            //遍历临时数组temp
            for(int j=0;j<n;++j){
                //计算出元素的当前排序位对应的值
                int subkey=(temp[j]/rate)%10;
                //计数
                buckets[subkey]++;
            }
            
            //计数排序：计算排序位值小于等于l的有多少个，则buckets[l]为排序位值为l的待排数据在当前排序位排序结果中的位置（位置=下标+1）
            for(int l=1;l<10;++l){
                buckets[l]=buckets[l-1]+buckets[l];
            }
            
            //进行排序位排序，遍历上一次排序结果
            for(int m=n-1;m>=0;--m){
                //计算当前元素的排序位值
                int subkey=(temp[m]/rate)%10;
                //由排序位值得到该元素在当前次排序结果中的下标
                int pos=buckets[subkey]-1;
                //根据下标，把当前元素填到合适位置
                A[pos]=temp[m];               
                //因为取了一个出来，所以计数数组对应值减一
                buckets[subkey]--;              
            }  
           //每排完一位后，往更高一位进行排序
           rate*=10;
        }         
        return A;
    }
}