Slow radix sort in C

Question

Мне нужно сортировать числа в массиве в порядке возрастания, а моя временная сложность должна быть O (n). Я использую сортировку radix, и это недостаточно быстро. Любые идеи, как я могу сделать свой код быстрее? Вот оно:

void radix(int *a, int n) { 

    int i; 
    int sorted[n]; 
    int number = 1; 
    int biggestNumber = -1; 

for(i = 0; i < n; i++){ 
    if(a[i] > biggestNumber) 
     biggestNumber = a[i]; } 


while (biggestNumber/number > 0){ 

int bucket[10] = { 0 }; 

    for (i = 0; i < n; i++) 
     bucket[(a[i]/number) % 10]++; 

    for (i = 1; i < 10; i++) 
     bucket[i] += bucket[i - 1]; 

    for (i = n - 1; i >= 0; i--) 
     sorted[--bucket[(a[i]/number) % 10]] = a[i]; 


    for (i = 0; i < n; i++) 
     a[i] = sorted[i]; 

     number*= 10; } } 

Answer 1

Комментария - Роды, кажется, работают только с положительными числами, если [я] отрицателен, то отрицательный индекс используются для ведра [...] и сортируют [... ]. Вы можете изменить это, чтобы отсортировать целые числа без знака, если целые числа со знаком не требуются. Нет проверки на переполнение по номеру * = 10. Сортировка выделяется из стека, что не будет работать, если n велико. Используйте malloc() для выделения пространства для сортировки.

Чтобы сделать вид быстрее:

Изменить основание системы счисления от 10 до 256. Для того, чтобы избежать возможного переполнения, проверьте 0 == (число = 256), чтобы вырваться из петли.

Измените направление сортировки radix на каждом проходе. 1-й проход от a до отсортированного, следующего прохода от отсортированного до a. Это проще всего с помощью пары указателей, которые меняются местами на каждом проходе, а затем после завершения сортировки, проверяя, были ли отсортированные данные в [], а если нет, скопируйте из отсортированного [] в [].

Сделайте ведро матрицей. Предполагая, что int - 32 бита, а база - 256, тогда ведро будет [4] [256]. Это позволяет сделать один проход над [], чтобы создать матрицу ковша. Если ints - 64 бита, bucket будет [8] [256].