|
# include <stdio.h>
# include <windows.h>
# define len 10
int FindMax(int a[], int n);
void radixSort(int a[], int n);
void countingSort(int a[], int n, int k);
int main(void)
{
?? ?int a[] = {123, 85, 10, 90, 235, 150, 310, 3};
?? ?int n = sizeof(a)/sizeof(int);
?? ?radixSort(a, n);
?? ?for(int i = 0; i < n; i++)
?? ??? ?printf("%d ", a[i]);
?? ?printf("\n");
?? ?system("pause");
?? ?return 0;
}
void radixSort(int a[], int n)
{
?? ?int max = FindMax(a, n);
?? ?//k为最大数的位数,分别由地位至高位进行计数排序
?? ?for(int k = 1; k <= max; k *= 10)
?? ?{
?? ??? ?countingSort(a, n, k);
?? ?}
}
void countingSort(int a[], int n, int k)
{?? ?
?? ?int * count = (int*)calloc(len, sizeof(int));
?? ?if(!count)
?? ??? ?exit(-1);
?? ?for(int i = 0; i < n; i++)
?? ??? ?count[a[i]/k%10]++;
?? ?for(int i = 1; i < len; i++)
?? ??? ?count[i] += count[i-1];
?? ?int * temp = (int*)malloc(sizeof(int)*n);
?? ?if(!temp)
?? ??? ?exit(-1);
?? ?for(int j = n-1; j >= 0; j--)
?? ??? ?temp[--count[a[j]/k%10]] = a[j];
?? ?for(int j = 0; j < n; j++)
?? ??? ?a[j] = temp[j];
?? ?free(count);
?? ?free(temp);
}
int FindMax(int a[], int n)
{
?? ?int max = a[0];
?? ?for(int i = 1; i < n; i++)
?? ?{
?? ??? ?if(a[i] > max)
?? ??? ??? ?max = a[i];
?? ?}
?? ?return max;
}
|