非比较排序概念
非比较排序是一种排序算法，它不是通过比较元素大小进行排序的，而是基于元素的特征和属性排序。这种排序方法在特定情况下，可以做到比元素比较排序（快排，归并）更有效率。尤其是在处理大量数据时。非比较要求输入数据满足一定条件，或者对数据特征进行合理利用
常见的非比较排序算法包括
- 计数排序
通常适用于范围比较小的整数排序，通过统计每个元素的出现次数，然后将元素按顺序放入数组
- 桶排序
将数据放到若干个桶中，随后对每个桶进行排序，最后再将所有桶的数据进行合并
- 基数排序
通过将待排序数值按位数分组，逐位进行排序，通常配合计数排序实现
计数排序
计数排序是一种非比较的排序算法，适用于特定条件下的排序，尤其是当待排序的元素范围较小其重复元素较多的时候。他的基本原理是利用一个额外的数组来记录每一个元素出现的次数，用次数来表达从而达到排序的目的，以下是排序的原理步骤
1.确定范围：首先确定待排序数组的元素的最大值和最小值
2.创建计数数组：根据范围创建一个技术数组，数组的大小通常为最大值和最小值的差+1，用于存放每个元素的出现次数
3.计数：遍历原始数组，统计每个元素相同的次数，对每个元素在计数数组中对应的位置进行计数。即：若元素为x，则计数数组的第x位置加一。
4.计算位置：通过累加计数数组的数值，得到每个元素在已排序数组中的最终位置。
5.排序输出，根据计数数组生成的已排序数组，遍历计数数组，按次数将对应的元素输出到结果数组中
计数排序的时间复杂度O（n+k），其中n是待排序元素的数量，k是计数数组的大小。
代码
public class CountSort {public static void sort(int[] array) {int minVal = array[0];int maxVal = array[0];//遍历数组找到最小值和最大值for (int i = 1; i < array.length; i++) {if (array[i] < minVal) {minVal = array[i];}if (array[i] > maxVal) {maxVal = array[i];}}//构建计数数组int[] count = new int[maxVal - minVal + 1];for (int i = 0; i < array.length; i++) {count[array[i] - minVal]++;}int index = 0;//将计数数组中的元素还原到原数组中for (int i = 0; i < count.length; i++) {while (count[i] > 0) {array[index] = i + minVal;index++;count[i]--;}}}
}
