计数排序基于以下思想:通过将不同元素的值与数组的索引号映射，对不同元素的出现次数进行计数并将其存储在另一个数组（例如频率数组）中。然后迭代频率数组以使用不同的元素及其出现次数，并以排序的方式将它们放入输出数组中。
示例:
为了理解计数排序，让我们考虑一下未排序的数组 A = [9, 1, 2, 5, 9, 9, 2, 1, 3, 3] 并讨论按升序对数组进行排序所采取的每个步骤。
第1步:在这一步中，找出A[]中最大的元素，即(9) 另一个名为频率 的数组以大小[max(A[ ])+1] 启动。然后迭代数组 A[ ]，通过将不同元素与索引号 频率映射来存储 频率 数组中每个不同元素的出现次数 数组。
第 2 步:在此步骤中，迭代频率数组以获取有关每个不同元素及其出现次数的信息，以供进一步使用构建排序数组。
当输入元素的范围不显着大于要排序的元素数量时，计数排序的使用效率最高。除此之外，同样的概念也可以用于负输入数据。
计数排序的实现
public class MyClass {
// 计数排序函数
static void countingsort(int Array[]) {
int n = Array.length;
int max = 0;
//查找数组中最大的元素
for (int i=0; i<n; i++) {
if(max < Array[i])
max = Array[i];
}
//创建一个freq数组来存储出现的次数
//给定数组中的每个唯一元素
int[] freq = new int[max+1];
for (int i=0; i<max+1; i++)
freq[i] = 0;
for (int i=0; i<n; i++)
freq[Array[i]]++;
//使用freq数组对给定数组进行排序
for (int i=0, j=0; i<=max; i++) {
while(freq[i]>0) {
Array[j] = i;
j++;
freq[i]--;
}
}
}
//打印数组的函数
static void PrintArray(int Array[]) {
int n = Array.length;
for (int i=0; i<n; i++)
System.out.print(Array[i] + " ");
System.out.println();
}
//测试代码
public static void main(String[] args) {
int[] MyArray = {9, 1, 2, 5, 9, 9, 2, 1, 3, 3};
System.out.println("原始数组");
PrintArray(MyArray);
countingsort(MyArray);
System.out.println("\n排序数组");
PrintArray(MyArray);
}
} 上面的代码将给出以下输出:
原始数组
9 1 2 5 9 9 2 1 3 3
排序数组
1 1 2 2 3 3 5 9 9 9 时间复杂度:
迭代输入数据的时间复杂度为θ(N)，其中N是未排序数组中的元素数量以及迭代频率数组的时间复杂度为θ(K)，其中K是输入范围数据。在所有情况下，计数排序的总体时间复杂度均为 θ(N+K)。