[数据结构与算法]java实现计数排序与基数排序

基数排序的正确性证明可以用数学归纳法，《算法导论》第三版习题8.3-3。里面需要一个概念：排序算法的稳定性。

//计数排序
package class03P;

import java.util.Arrays;

public class Code01P_CountSort {
    // 计数排序例子，如按给定一个数组，数组中的元素是员工的年龄，范围是0~200，数据大小限制在一定的范围内的排序
    // 计数排序的时间复杂度是O(N)
    public static void countSort(int[] arr){
        if(arr == null ||arr.length < 2) return;
        int[] help = new int[200];
        for (int i = 0; i < arr.length; i++) {
            help[arr[i]]++;
        }
        int index = 0;
        for (int i = 0; i < help.length; i++) {
            while(help[i]-- > 0){
//                help[i]--;
                arr[index++] = i;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {92, 97, 150, 50, 64, 12, 38, 60, 12};
        System.out.println(Arrays.toString(arr));
        countSort(arr);
        System.out.println(Arrays.toString(arr));
    }

}

package class03P;


import java.util.Arrays;

public class Code02P_RadixSort {

    public static void RadixSort(int[] arr){
        if(arr == null || arr.length < 2) return;
        int d = maxBits(arr);
        int[] bucket = new int[10];
        int[] help = new int[arr.length];

        for (int i = 1; i <= d; i++) {
            for (int j = 0; j < bucket.length; j++) {//统计arr数组其他数位的值时，bucket要清零
                bucket[j] = 0;
            }
            for (int j = 0; j < arr.length; j++) {
                bucket[getDigit(arr[j], i)]++;
            }

            for (int j = 1; j < bucket.length; j++) {
                bucket[j] += bucket[j - 1];
            }

            for (int j = arr.length - 1; j >= 0; j--) {
                help[--bucket[getDigit(arr[j], i)]] = arr[j];
            }

            System.arraycopy(help, 0, arr, 0,help.length);//最后一个参数是要拷贝元素的个数
        }

    }

    public static int maxBits(int[] arr){//arr是一个自然数数组，返回值的范围是>=0&&<=9的整数(0数组时返回0)
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(arr[i], max);
        }
        int res = 0;
        for(; max > 0; max /= 10){
            res++;
        }
        return res;
    }

    public static int getDigit(int a, int d){
        return ((a / ((int)Math.pow(10, d - 1))) % 10);
    }
    public static void main(String[] args) {
        int[] arr = {23, 345, 1, 0};
        RadixSort(arr);
        System.out.println(Arrays.toString(arr));
    }

}