Repository navigation
Expand file tree
/
Copy pathradixSort.c
More file actions
92 lines (76 loc) · 2.17 KB
/
Copy pathradixSort.c
File metadata and controls
92 lines (76 loc) · 2.17 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<stdio.h>
#include<malloc.h>
void radixSort(int *a, int count);
void countSort(int *bitNumber, int count, int *newA, int *c, int *a);
void showArray(int *a, int count);
void showArray(int *a, int count){
int i;
for(i = 0; i < count; i++){
printf("%d ", a[i]);
}
printf("\n");
}
void countSort(int *bitNumber, int count, int *newA, int *c, int *a){
int i;
//从个位-->十位-->百位,每一次调用这个函数,辅助空间都必须初始化为0;
for(i = 0; i < 10; i++){
c[i] = 0;
}
for(i = 0; i < count; i++){
c[bitNumber[i]]++;
}
for(i = 1; i < 10; i++){
c[i] += c[i-1];
}
for(i = count-1; i >= 0; i--){
newA[c[bitNumber[i]]-1] = a[i]; //a[i]与原先所取的位顺序一致
c[bitNumber[i]]--;
}
}
void radixSort(int *a, int count){
int *bitNumber;
int *newA;
int c[10] = {0};
int i;
//个位进行排序
bitNumber = (int *)malloc(sizeof(int) * count);
newA = (int *)malloc(sizeof(int) * count);
for(i = 0; i < count; i++){
bitNumber[i] = a[i]%10;
}
countSort(bitNumber, count, newA, c, a); //bitNumber:代表要排的数字;newA:代表最终排行的新空间
// c:代表辅助空间 a:代表原先数字
for(i = 0; i < count; i++){
a[i] = newA[i];
}
//十位进行排序
for(i = 0; i < count; i++){
bitNumber[i] = a[i]/10%10;
}
countSort(bitNumber, count, newA, c, a);
for(i = 0; i < count; i++){
a[i] = newA[i];
}
//百位排序
for(i = 0; i < count; i++){
bitNumber[i] = a[i]/100%10;
}
countSort(bitNumber, count, newA, c, a);
for(i = 0; i < count; i++){
a[i] = newA[i];
}
//千位排序
for(i = 0; i < count; i++){
bitNumber[i] = a[i]/1000%10;
}
countSort(bitNumber, count, newA, c, a);
for(i = 0; i < count; i++){
a[i] = newA[i];
}
}
void main(void){
int a[] = {23, 1000, 90, 34, 2, 6, 3, 444, 555, 666, 777, 888, 999, 111, 222};
int count = sizeof(a)/sizeof(int);
radixSort(a, count);
showArray(a, count);
}