c Radix sort Radix sort implementation method
- 2020-06-03 08:07:30
- OfStack
Classical sorting algorithm - radix sort Radix sort
The principle is similar to bucket sorting, where you always need 10 buckets and use them multiple times
First, fill the bucket with the value of the units digit, that is, if the units digit is 1, put it into the no.1 bucket; if the units digit is 9, put it into the No.9 bucket, temporarily ignore the 10-digit number
For example,
The array to be sorted [62,14,59,88,16] is simple
Allocate 10 buckets, numbered 0-9, and put them into the buckets in order of the units digits, so that they look like this
| 0 | 0 | 62 | 0 | 14 | 0 | 16 | 0 | 88 | 59 |
| 0 b| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |0 bucket number
Take the Numbers out of the bucket,
Output :[62,14,16,88,59]
Enter the bucket again, but this time with a 10-digit number, enter the corresponding bucket, and look like this:
Because the previous side has done the ordering of the units digit, when the 10 digits are equal, the ones digit goes into the bucket in order from small to large, that is to say, the bucket is still in order when it is finished
| 0 | 14,16 | 0 | 0 | 0 | 59 | 62 | 0 | 88 | 0 |
| 0 b| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |0 bucket number
Because there are no Numbers bigger than 100, there are no hundreds, so when we're done here, we can just take them out
Final output :[14,16,59,62,88]
The code is for reference only
/// <summary>
/// Radix sort
/// convention : Not in the Numbers to be sorted 0, If the number in a bucket is zero 0 Indicates that the bucket is not in use , Just skip the output
/// </summary>
/// <param name="unsorted"> For row array </param>
/// <param name="array_x"> The first bucket array 1 The length of the dimension </param>
/// <param name="array_y"> The first bucket array 2 The length of the dimension </param>
static void radix_sort(int[] unsorted, int array_x = 10, int array_y = 100)
{
for (int i = 0; i < array_x/* The maximum number is not exceeded 999999999...(array_x a 9) */; i++)
{
int[,] bucket = new int[array_x, array_y];
foreach (var item in unsorted)
{
int temp = (item / (int)Math.Pow(10, i)) % 10;
for (int l = 0; l < array_y; l++)
{
if (bucket[temp, l] == 0)
{
bucket[temp, l] = item;
break;
}
}
}
for (int o = 0, x = 0; x < array_x; x++)
{
for (int y = 0; y < array_y; y++)
{
if (bucket[x, y] == 0) continue;
unsorted[o++] = bucket[x, y];
}
}
}
}
static void Main(string[] args)
{
int[] x = { 999999999, 65, 24, 47, 13, 50, 92, 88, 66, 33, 22445, 10001, 624159, 624158, 624155501 };
radix_sort(x);
foreach (var item in x)
{
if (item > 0)
Console.WriteLine(item + ",");
}
Console.ReadLine();
}