它是一種基於鍵的分類技術,即根據小整數的鍵收集物件。 計數排序計算物件的出現次數並儲存其鍵值。 通過新增先前的鍵元素並分配給物件來形成新陣列。
O(n + k)
是最壞的情況,其中n
是元素的數量,k
是輸入的範圍。O(k)
- k
是輸入範圍。複雜度 | 最好情況 | 平均情況 | 最壞情況 |
---|---|---|---|
時間複雜度 | Ω(n+k) | θ(n+k) | O(n+k) |
空間複雜度 | - | - | O(k) |
演算法
第1步,開始
第2步,儲存輸入陣列。
第3步,按物件出現次數計算鍵值。
第4步,通過新增以前的鍵元素並分配給物件來更新陣列
第5步,通過將物件替換為新陣列並使用`key = key-1`進行排序
第6步,停止
使用C語言實現上面排序演算法,程式碼如下 -
#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("Enter 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;
}