The c language implements radix sort resolution and code samples

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; 
} 
void RadixSort(int data[], int n){ 
  //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); 
  //maxNum times radix sort 
  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}; 
  RadixSort(Array, 10); 
  for(int i = 0; i < 10; i++){ 
    printf("%d ", Array[i]); 
  } 
  printf("\n"); 
  return 0; 
} 

conclusion

That's all for this article about the c language implementation of radix sort parsing and code samples, I hope to help you. Interested friends can continue to see the site other related topics, if there are shortcomings, welcome to point out the message. Thank you for your support!