【数据结构计数排序】计数排序

非比较排序概念

非比较排序是一种排序算法，它不是通过比较元素大小进行排序的，而是基于元素的特征和属性排序。这种排序方法在特定情况下，可以做到比元素比较排序（快排，归并）更有效率。尤其是在处理大量数据时。非比较要求输入数据满足一定条件，或者对数据特征进行合理利用

常见的非比较排序算法包括

• 计数排序

通常适用于范围比较小的整数排序，通过统计每个元素的出现次数，然后将元素按顺序放入数组

• 桶排序

将数据放到若干个桶中，随后对每个桶进行排序，最后再将所有桶的数据进行合并

• 基数排序

通过将待排序数值按位数分组，逐位进行排序，通常配合计数排序实现

计数排序

计数排序是一种非比较的排序算法，适用于特定条件下的排序，尤其是当待排序的元素范围较小其重复元素较多的时候。他的基本原理是利用一个额外的数组来记录每一个元素出现的次数，用次数来表达从而达到排序的目的，以下是排序的原理步骤

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]--;
            }
        }
    }
}