By

Contents 
/**
 * 8.计数排序
 */
public static void countSort(int[] a, int k) {
    int[] C = new int[k + 1];// 构造数组C
    int length = a.length, sum = 0;// 获取A数组大小用于构造B数组
    int[] B = new int[length];// 构造数组A
    for (int i = 0; i < length; i++) {
        C[a[i]] += 1;// 统计A中各元素的个数，存入C数组
    }
    for (int i = 0; i < C.length; i++) {// 修改C数组
        sum += C[i];
        C[i] = sum;
    }
    for (int i = length - 1; i >= 0; i--) {// 遍历数组A 把数组A的值赋到B中对应位置
        // 倒序遍历保证稳定性
        B[C[a[i]] - 1] = a[i];// 将A中该元素放到排序后数组B中指定的位置
        C[a[i]]--;// 将C中该元素-1，方便存放下一个同样大小的元素
    }
    printSort(B);
}

static int[] countSort2(int[] a, int range/* 数组元素的范围 */) {
    int count[] = new int[range];
    for (int i = 0; i < a.length; i++) {
        count[a[i]]++;
    }
    for (int i = 1; i < count.length; i++) {
        count[i] += count[i - 1];
    }
    int sortArr[] = new int[a.length];
    for (int i = 0; i < sortArr.length; i++) {
        count[a[i]]--;
        sortArr[count[a[i]]] = a[i];
    }
    return sortArr;
}

/**
 * 9.基数排序
 */
public static void radixSort(int[] data, int radix, int d) {
    // 缓存数组
    int[] tmp = new int[data.length];
    // buckets用于记录待排序元素的信息
    // buckets数组定义了max-min个桶
    int[] buckets = new int[radix];

    for (int i = 0, rate = 1; i < d; i++) {

        // 重置count数组，开始统计下一个关键字
        Arrays.fill(buckets, 0);
        // 将data中的元素完全复制到tmp数组中
        System.arraycopy(data, 0, tmp, 0, data.length);

        // 计算每个待排序数据的子关键字
        for (int j = 0; j < data.length; j++) {
            int subKey = (tmp[j] / rate) % radix;
            buckets[subKey]++;
        }

        for (int j = 1; j < radix; j++) {
            buckets[j] = buckets[j] + buckets[j - 1];
        }

        // 按子关键字对指定的数据进行排序
        for (int m = data.length - 1; m >= 0; m--) {
            int subKey = (tmp[m] / rate) % radix;
            data[--buckets[subKey]] = tmp[m];
        }
        rate *= radix;
    }

}
Contents