Count Sort Back

  • 計數排序: 計算某元素前有k個小於它的元素, 則該元素放在第k+1位
  • 时间复杂度: (最好,平均,最壞情況)
  • 空間複雜度: /
  • 稳定性: 稳定
  • 适用情况: 小範圍整數, 且範圍不超過個數的量級
/* A[] to store data, B[] to store sorted data */
void COUNTSORT(int A[], int B[], int k, int array_size)
{
    int C[MAXSIZE];
    for (int i = 0; i <= k; i++)
        C[i] = 0;
    for (int j = 0; j <= array_size - 1; j++)
        C[A[j]]++;
    for (int i = 1; i <= k; i++)
        C[i] = C[i] + C[i - 1];

    for (int j = array_size - 1; j >= 0; j--)
    {
        B[C[A[j]] - 1] = A[j];
        C[A[j]]--;
    }
}
Empty Comments
Sign in GitHub

As the plugin is integrated with a code management system like GitLab or GitHub, you may have to auth with your account before leaving comments around this article.

Notice: This plugin has used Cookie to store your token with an expiration.