这是一种基于密钥的排序技术, 即根据是小整数的密钥收集对象。计数排序计算对象的出现次数并存储其键值。通过添加先前的关键元素并分配给对象来形成新的数组。
复杂时间复杂度：O（n + k）是最坏的情况, 其中n是元素数, k是输入范围。
空间复杂度：O（k）k是输入范围。
| 复杂 | 最好的情况 | 平均情况 | 最差的情况 |
|---|---|---|---|
| 时间复杂度 | Ω（n + k） | θ（n + k） | O（n + k） |
| Space Complexity | O(k) |
- 当范围不大于对象数时有效。
- 这不是基于比较的复杂性。
- 它也用作不同算法的子算法。
- 它使用部分哈希技术来计数发生次数。
- 它还用于负输入。
- 步骤1开始
- 步骤2存储输入数组
- 步骤3通过出现对象的数量计算键值
- 步骤4通过添加先前的关键元素并分配给对象来更新阵列
- 步骤5通过将对象替换为新数组和key = key-1进行排序
- 步骤6停止
#include <
stdio.h>
void counting_sort(int A[], int k, int n){int i, j;
int B[15], C[100];
for (i = 0;
i <
= k;
i++)C[i] = 0;
for (j = 1;
j <
= n;
j++)C[A[j]] = C[A[j]] + 1;
for (i = 1;
i <
= k;
i++)C[i] = C[i] + C[i-1];
for (j = n;
j >
= 1;
j--){B[C[A[j]]] = A[j];
C[A[j]] = C[A[j]] - 1;
}printf("The Sorted array is : ");
for (i = 1;
i <
= n;
i++)printf("%d ", B[i]);
}/*End of counting_sort()*/ /*The main() begins*/int main(){int n, k = 0, A[15], i;
printf("Enter the number of input : ");
scanf("%d", &
n);
printf("\nEnter the elements to be sorted :\n");
for (i = 1;
i <
= n;
i++){scanf("%d", &
A[i]);
if (A[i] >
k) {k = A[i];
}}counting_sort(A, k, n);
printf("\n");
return 0;
}
