計數排序

它是一種基於鍵的分類技術，即根據小整數的鍵收集對象。 計數排序計算對象的出現次數並存儲其鍵值。 通過添加先前的鍵元素並分配給對象來形成新數組。

1. 複雜性

• 時間複雜度 ：O(n + k)是最壞的情況，其中n是元素的數量，k是輸入的範圍。
• 空間複雜度 ：O(k)- k是輸入範圍。

2. 計數排序的限制

• 範圍不大於對象數時有效。
• 它不是基於比較的複雜度。
• 它也被用作不同演算法的子演算法。
• 它使用部分散列技術來計算出現次數。
• 它也用於負輸入。

演算法

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