C에서 느린 기수 정렬

Question

배열의 숫자를 오름차순으로 정렬해야하고 시간 복잡성은 O (n)이어야합니다. 기수 정렬을 사용하고 있으며 충분히 빠르지 않습니다. 어떤 아이디어로 내 코드를 더 빨리 만들 수 있습니까? 여기입니다 :

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

코멘트 - 정렬 만 [내가] 음수이면, 음의 색인이 버킷에 사용되는, 양수 작업을 나타납니다 [...]와 [분류 ... ]. 부호있는 정수가 필요하지 않은 경우이 값을 변경하여 부호없는 정수를 정렬 할 수 있습니다. number * = 10에 오버플로가 있는지 검사 할 필요가 없습니다. 정렬은 스택에서 할당되고 있습니다. n이 큰 경우에는 작동하지 않습니다. malloc()을 사용하여 정렬 할 공간을 할당하십시오.

는 빠르게 정렬하기 :

변경

256 10 기수의베이스 == 0 (번호 * = 256), 루프 탈옥 확인 가능한 오버 플로우를 방지하기 위해.

각 패스에서 기수 정렬 방향을 바꿉니다. a에서 sorted 로의 첫 번째 전달, a에서 sorted 로의 다음 전달. 정렬이 완료된 후 정렬 된 데이터가 []로 끝나는 지 확인하고 정렬되지 않은 경우 정렬 된 []에서 []로 복사하는 것을 확인하는 한 쌍의 포인터를 사용하는 것이 가장 쉽습니다.

버킷을 행렬로 만듭니다. int가 32 비트이고 기본이 256이라고 가정하면 버킷은 [4] [256]이됩니다. 이것은 버킷 행렬을 만들기 위해 []에 대한 단일 패스를 허용합니다. int가 64 비트이면 버킷은 [8] [256]이됩니다.