#include<iostream>usingnamespace std;
constint N =10;
intmaxm(int arr[], int n) {
int max = arr[0];
for (int i =1; i < n; i++)
{
if (arr[i] > max)
{
max = arr[i];
}
}
return max;
}
intminm(int arr[], int n) {
int min = arr[0];
for (int i =1; i < n; i++)
{
if (arr[i] < min)
{
min = arr[i];
}
}
return min;
}
voidcountingSort(int arr[], int n) {
int min = minm(arr, n);
int max = maxm(arr, n);
int range = max - min +1;
int count[range]={};
int output[n];
for (int i =0; i < n; i++)
count[arr[i] - min]++;
for (int i =1; i < range; i++)
count[i] += count[i -1];
for (int i = n -1; i >=0; i--) {
output[count[arr[i] - min] -1] = arr[i];
count[arr[i] - min]--;
}
for (int i =0; i < n; i++)
arr[i] = output[i];
}
intmain() {
int n =7;
int arr[7] = {3, 5, 1, 1, 4, 2, 1};
cout <<"Input arr: ";
for (int i =0; i < n; i++) {
cout << arr[i] <<" ";
}
cout <<"\n";
countingSort(arr, n); // Sort elements in ascending order
cout <<"Output arr: ";
for (int i =0; i < n; i++) {
cout << arr[i] <<" ";
}
cout <<"\n";
}
此实现也适用于负数。
计数排序算法的复杂度
时间复杂度
平均情况
计数排序对所有 n 项进行两次迭代,对计数数组进行一次迭代。因此,它的时间复杂度为 O(n+b),其中 b 是输入的范围。由于 b 通常较小,所以计数排序的时间复杂度可以说是 [Big Theta]:O(n)。
最坏情况
最坏情况下的时间复杂度为 [Big O]:O(n)。
最佳情况
最佳情况下的时间复杂度是 [Big Omega]:O(n)。它与最坏情况下的时间复杂度相同。
空间复杂度
计数排序算法的空间复杂度为 O(n+b),其中 b 是输入的范围。它来自于 count&output 数组。有时 b 可以比 n 大,但如果 b 小,时间复杂度可以说是 O(n)。
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.