How to write a radix sort algorithm using C#

How to use C# to write a radix sorting algorithm

Introduction:
Radix Sort (Radix Sort) is a non-comparative sorting algorithm suitable for integers Sort. Its basic idea is to sort the elements to be sorted from low to high to obtain an ordered sequence. Compared with other sorting algorithms, radix sorting has lower time complexity and stability.

Implementation steps:

1. Find the largest number in the array to be sorted and determine its number of digits.
2. According to the maximum number of digits, proceed to the next step from low to high.
3. Perform counting sorting on the array to be sorted, and group according to the current number.
4. Recombine the grouped array into a new array to be sorted.
5. Repeat steps 3 and 4 until all digits have been compared.

Code sample:
The following is a sample code for the radix sorting algorithm written in C#:

using System;

public class RadixSort
{
    public static void Sort(int[] array)
    {
        int max = GetMaxValue(array);
        int digits = GetDigits(max);

        for (int i = 0; i < digits; i++)
        {
            CountingSort(array, i);
        }
    }

    private static int GetMaxValue(int[] array)
    {
        int max = array[0];
        for (int i = 1; i < array.Length; i++)
        {
            if (array[i] > max)
            {
                max = array[i];
            }
        }
        return max;
    }

    private static int GetDigits(int number)
    {
        int digits = 0;
        while (number > 0)
        {
            number /= 10;
            digits++;
        }
        return digits;
    }

    private static void CountingSort(int[] array, int digit)
    {
        int[] count = new int[10];
        int[] sortedArray = new int[array.Length];

        for (int i = 0; i < array.Length; i++)
        {
            int digitValue = GetDigitValue(array[i], digit);
            count[digitValue]++;
        }

        for (int i = 1; i < count.Length; i++)
        {
            count[i] += count[i - 1];
        }

        for (int i = array.Length - 1; i >= 0; i--)
        {
            int digitValue = GetDigitValue(array[i], digit);
            int index = count[digitValue] - 1;
            sortedArray[index] = array[i];
            count[digitValue]--;
        }

        for (int i = 0; i < array.Length; i++)
        {
            array[i] = sortedArray[i];
        }
    }

    private static int GetDigitValue(int number, int digit)
    {
        for (int i = 0; i < digit; i++)
        {
            number /= 10;
        }
        return number % 10;
    }
}

public class Program
{
    public static void Main(string[] args)
    {
        int[] array = { 170, 45, 75, 90, 802, 24, 2, 66 };
        
        Console.WriteLine("Before sorting:");
        foreach (int num in array)
        {
            Console.Write(num + " ");
        }
        
        RadixSort.Sort(array);
        
        Console.WriteLine("

After sorting:");
        foreach (int num in array)
        {
            Console.Write(num + " ");
        }
    }
}

Running results:

Before sorting:
170 45 75 90 802 24 2 66 

After sorting:
2 24 45 66 75 90 170 802

Summary:
The radix sort algorithm is a relatively efficient sorting algorithm that can quickly sort integer arrays. By sorting the array to be sorted from low to high, an ordered array is finally obtained. When using C# to write a radix sorting algorithm, we need to first find the maximum value and number of digits of the array to be sorted, then count and sort each digit, and finally recombine the sorted array to obtain an ordered result. As can be seen from the running results of the sample code, the radix sort algorithm can correctly sort the array.

The above is the detailed content of How to write a radix sort algorithm using C#. For more information, please follow other related articles on the PHP Chinese website!