с бисером хотел бы помочь

Question

У меня есть большой список положительных целых чисел в массиве, и я хотел бы использовать сортировку по бусам, но оказалось, что она не очень хорошо документированау кого-нибудь есть код для сортировки бус?

Answer 1

Эта страница имеет реализации на нескольких языках, включая C: http://rosettacode.org/wiki/Sorting_algorithms/Bead_sort

Answer 2

С В этом вопросе появилась модификация сортировки шариков, которая использует O(N) дополнительное пространство вместо O(N*k), как в версии Rosetta Code.

void sort(int A[], int N)
{
    int i, j;
    int *R = calloc(N, sizeof(int));

    do for (i = j = 0; i < N; i++) 
      if (A[i]) { R[j++]++; A[i]--; }
    while (j);

    for (j = N, i = 0; i < N; i++)
      A[i] = R[--j]; // A is now sorted ascending.

    free(R);
}

Тем не менее, это по крайней мере в 10 раз медленнее, чем qsort, и оно становится тем хуже, чем больше элементы массива. Я бы не рекомендовал его использовать.