计数排序算法描述+代码实现，基数排序算法描述+代码实现
计数排序的说明： 计数排序（Counting sort）是一种稳定的线性时间排序算法。
当输入的元素是n个0到k之间的整数时，它的运行时间是Θ(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。
由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。例如：计数排序是用来排序0到100之间的数字的最好的算法，但是它不适合按字母顺序排序人名。但是，计数排序可以用在基数排序算法中，能够更有效的排序数据范围很大的数组。
通俗地理解，例如有10个年龄不同的人，统计出有8个人的年龄比A小，那A的年龄就排在第9位，用这个方法可以得到其他每个人的位置，也就排好了序。当然，年龄有重复时需要特殊处理（保证稳定性），这就是为什么最后要反向填充目标数组，以及将每个数字的统计减去1的原因。
/**
* @author zhailz
* 计数排序（Counting sort）是一种稳定的线性时间排序算法。
* 计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置
*/
public class CountSort {
public static void main(String[] args) {
//排序的数组
int a[] = { 100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 95 };
int b[] = countSort(a);
for (int i : b) {
System.out.print(i + " ");
}
System.out.println();
}
/*
* 找出待排序的数组中最大和最小的元素
* 统计数组中每个值为i的元素出现的次数，存入数组 C 的第 i 项
* 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
* 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
* */
public static int[] countSort(int[] a) {
int b[] = new int[a.length];
//获得数组的最大值和最小值
int max = a[0], min = a[0];
for (int i : a) {
if (i > max) {
max = i;
}
if (i < min) {
min = i;
}
}
//这使得计数排序对于数据范围很大的数组，需要大量时间和内存
//这里k的大小是要排序的数组中，元素大小的极值差+1
int k = max - min + 1;
int c[] = new int[k];
for (int i = 0; i < a.length; ++i) {
c[a[i] - min] += 1;//优化过的地方，减小了数组c的大小
}
//前面有几个比我小的值
for (int i = 1; i < c.length; ++i) {
c[i] = c[i] + c[i - 1];
}
PrintUtil.printArray(a);
PrintUtil.printArray(c);
for (int i = a.length - 1; i >= 0; --i) {
//主要是考虑到了数组的中数字的重复性
c[a[i] - min] = c[a[i] - min] - 1;
int index = c[a[i] - min];
b[index] = a[i];//按存取的方式取出c的元素
PrintUtil.printArray(b);
}
return b;
}
public static int[] countingSort(int[] A) {
int[] B = new int[A.length];
// 假设A中的数据a'有，0<=a' && a' < k并且k=100
int k = 100 + 1;
countingSort(A, B, k);
return B;
}
private static void countingSort(int[] A, int[] B, int k) {
int[] C = new int[k];
// 计数
for (int j = 0; j < A.length; j++) {
int a = A[j];
C[a] += 1;
}
// 求计数和
for (int i = 1; i < k; i++) {
C[i] = C[i] + C[i - 1];
}
PrintUtil.printArray(A);
PrintUtil.printArray(C);
// 整理
for (int j = A.length - 1; j >= 0; j--) {
int a = A[j];
B[C[a] - 1] = a;
C[a] -= 1;
PrintUtil.printArray(B);
PrintUtil.printArray(C);
}
}
}
基数排序的说明：
/**
* @author zhailz
* 基数排序的时间复杂度是O(k·n)，其中n是排序元素个数，k是数字位数。
* 注意这不是说这个时间复杂度一定优于O(n·log(n))，k的大小取决于数字位的选择（比如比特位数），
* 和待排序数据所属数据类型的全集的大小；k决定了进行多少轮处理，而n是每轮处理的操作数目。
*/
public class RadixSort {
/**
* 基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机(Tabulation Machine)上的贡献。
* 它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，
* 从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
*
* */
// 求取的数组中最大数的位数
public static int maxbit(int data[], int n) //辅助函数，求数据的最大位数
{
int maxData = data[0]; ///< 最大数
/// 先求出最大数，再求其位数，这样有原先依次每个数判断其位数，稍微优化点。
for (int i = 1; i < n; ++i) {
if (maxData < data[i])
maxData = data[i];
}
int d = 1;
int p = 10;
while (maxData >= p) {
maxData /= 10;
++d;
}
return d;
}
public static void radixsort(int data[], int n) //基数排序
{
int d = maxbit(data, n);
int[] tmp = new int[n];
int[] count = new int[10]; //计数器
int i, j, k;
int radix = 1;
for (i = 1; i <= d; i++) //进行d次排序
{
for (j = 0; j < 10; j++)
count[j] = 0; //每次分配前清空计数器
for (j = 0; j < n; j++) {
k = (data[j] / radix) % 10; //统计每个桶中的记录数
count[k]++;
}
for (j = 1; j < 10; j++)
count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
for (j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
{
k = (data[j] / radix) % 10;
tmp[count[k] - 1] = data[j];
count[k]--;
}
for (j = 0; j < n; j++) //将临时数组的内容复制到data中
data[j] = tmp[j];
radix = radix * 10;
}
}
public static void main(String[] args) {
int[] data = { 73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100 };
RadixSort.radixsort(data, 3);
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + " ,");
}
}
}