# The c language implements radix sort resolution and code samples

• 2020-06-01 10:29:38
• OfStack

1.

Radix sort (radixsort) is a kind of "allocated sort" (distributionsort), also known as "bucket method" (bucketsort) or binsort. As the name implies, it allocates the elements to be sorted to some "buckets" by means of partial information of key values.

2. There are two ways to implement radix sort:

The highest bit first (MostSignificantDigitfirst) method, referred to as MSD method, first sorts and groups according to k1, and then sorts and groups according to k2, and then sorts and groups according to k2, and then sorts and groups according to kd, and then sorts and groups according to kd. Connect the groups, and you get an ordered sequence.

The lowest order first (LeastSignificantDigitfirst) method, referred to as LSD method, starts with kd, then sorts kd-1, and then repeats, until after sorting k1, an ordered sequence is obtained.

3. The principle and code implementation of LSD radix sort are as follows:

Step 1

Suppose there was a string of values as follows:

73,22,93,43,55,14,28,65,39,81

First, according to the value of the units digit, the values are assigned to the buckets numbered 0 to 9 when the values are visited:

0
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39

Step 2

Next, the values in these buckets are concatenated to form the following sequence:

81,22,73,93,43,14,55,65,28,39

Then another allocation is made, this time according to 10 digits:

0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93

Step 3

Next, the values in these buckets are concatenated to form the following sequence:

14,22,28,39,43,55,65,73,81,93

Now the whole sequence is sorted; If the sorted object has more than 3 digits, continue until the highest digit.

``````
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int getDigitNum(int x){
if(x == 0) return 1;
int res = 0;
while(x){
res ++;
x /= 10;
}
return res;
}
//find the Maximum and its digit number
int Max = data[0];
for(int i = 1; i < n; i++){
if(Max < data[i]) Max = data[i];
}
int maxNum = getDigitNum(Max);
int divisor = 1;
for(int k = 0; k < maxNum; k++){
vector<int> g[10];//g[i] Included in the " The bottom " Numbers are i the data[] Elements in an array
for(int i = 0; i < 10; i++) g[i].clear();
for(int i = 0; i < n; i++){
int tmp = data[i] / divisor % 10;
g[tmp].push_back(data[i]);
}
int cnt = 0;
for(int i = 0; i < 10; i++){
for(int j = 0; j < g[i].size(); j++){
data[cnt++] = g[i][j];
}
}
divisor *= 10;
}
}
int main(){
int Array[10] = {73,22,93,43,55,14,28,65,39,81};