用Java实现计数排序
计数排序也是一个简单易懂的排序算法，排序思路运用了桶排序中“桶”的概念，适合对数据范围不大的数组进行排序。
举个例子，一门考试满分100分，分数范围从0分到100分。我们可以分成101个桶（最大值 - 最小值 + 1），每个桶内对应的考试分数相同。这样我们就不需要在桶内进行排序，只需要依次扫描每个桶，将桶内数据依次输出到数组中，就得到有序数组了。由此看出，计数排序其实是桶排序的一种特殊情况。
具体如何实现呢？
计数排序实现可分为四步：
①、找出待排序的数组中最大值和最小值，划分区间（即桶的个数）；
②、统计待排序数组每个值出现的次数，创建一个新数组（长度为区间长度），记录频次；
③、将新数组当前项等于当前项和前一项相加；（由此，新数组的最后一项即是待排序数组的长度。）
④、逆向将待排序元素填充到临时数组中，再重新赋值给待排序元素，完成排序。
代码实现如下：
import org.junit.Test;
import java.util.Arrays;
/**
* 计数排序
* 1. 找出待排序的A数组中最大和最小的元素
* 2. 统计数组中每个值为i的元素出现的次数，存入数组B中的第i项
* 3. 对所有的计数累加（从新数组的第一个元素开始，每一项和前一项相加）
* 4. 反向填充目标数组：将每个元素i放在新数组C（B[i]）项，每放一个元素就将B[i]减1.
*/
public class CountingSort {
/**
* 计数排序算法实现
* @param array 待排序数组
*/
public void countingSort(int[] array) {
// 1. 找出待排序的A数组中最大和最小的元素
// 求出待排序数组的最大值，最小值，找出取值区间
int max = array[0];
int min = array[0];
for (int i = 0; i < array.length; i++) {
if (max < array[i]) {
max = array[i];
}
if (min > array[i]) {
min = array[i];
}
}
// 2. 统计数组中每个值为i的元素出现的次数，存入数组B中的第i项
// 定义数组B
// 桶的个数，也即数组B的长度
int bucketSize = max - min + 1;
int[] B = new int[bucketSize];
for (int j = 0; j < array.length; j++) {
int bucketIndex = array[j] - min;
B[bucketIndex] += 1;
}
// 3. 对所有的计数累加（从新数组的第一个元素开始，每一项和前一项相加）
for (int i = 0; i < bucketSize; i++) {
if (i > 0) {
B[i] = B[i] + B[i - 1];
}
}
// 4. 反向填充目标数组：将每个元素i放在新数组C（B[i]）项，每放一个元素就将B[i]减1.
// 定义数组C
int[] C = new int[array.length];
for (int j = array.length - 1; j >= 0; j--) {
int bucketIndex = array[j] - min;
C[B[bucketIndex] - 1] = array[j];
B[bucketIndex] -= 1;
}
// 原数组重新复制
for (int i = 0; i < array.length; i++) {
array[i] = C[i];
}
}
我们再写一段测试代码，看一下是否能达到我们的预期。
public void test() {
// 准备一个数组
int[] array = new int[7];
array[0] = 3;
array[1] = 1;
array[2] = 0;
array[3] = 6;
array[4] = 4;
array[5] = 8;
array[6] = 9;
System.out.println("排序前：");
System.out.println(Arrays.toString(array));
countingSort(array);
System.out.println("排序后：");
System.out.println(Arrays.toString(array));
}
// 打印结果
排序前：
[3, 1, 0, 6, 4, 8, 9]
排序后：
[0, 1, 3, 4, 6, 8, 9]
可以看到，代码实现就此完成。我们再来分析一下计数排序的时间复杂度、空间复杂度及稳定性问题。
①、计数排序不涉及元素的比较，只有对待排序数组及用于计数数组的遍历操作，因此时间复杂度为O(n+k)。k代表桶的个数，也即数据范围。
②、在计数排序中需要开辟额外的空间，存储用于计数数组（长度k）和用于临时存储排序结果的数组（长度n），因此空间复杂度为O(n+k)。
③、在计数排序中，我们采用逆向填充数组的方式，保证了相同值的相对位置固定，因此计数排序是一种稳定的排序算法。
④、由①和②知计数排序适合数据范围小的数组进行排序，当数据范围大时，需要大量的时间和空间。
好了，今天的分享就到这里了，期待下篇文章见。