Bagaimana untuk menulis algoritma isihan radix menggunakan C#

WBOY
Lepaskan: 2023-09-19 09:12:21
asal
822 orang telah melayarinya

Bagaimana untuk menulis algoritma isihan radix menggunakan C#

Cara menggunakan C# untuk menulis algoritma isihan radix

Pengenalan:
Radix Sort ialah algoritma isihan bukan perbandingan yang sesuai untuk mengisih integer. Idea asasnya adalah untuk mengisih unsur-unsur yang hendak diisih dari rendah ke tinggi untuk mendapatkan urutan yang teratur. Berbanding dengan algoritma pengisihan lain, pengisihan radix mempunyai kerumitan dan kestabilan masa yang lebih rendah.

Langkah pelaksanaan:

  1. Cari nombor terbesar dalam tatasusunan untuk diisih dan tentukan bilangan digitnya.
  2. Mengikut bilangan digit maksimum, teruskan ke langkah seterusnya dari rendah ke tinggi.
  3. Lakukan pengisihan mengira pada tatasusunan yang hendak diisih dan kumpulan mengikut nombor semasa.
  4. Satukan semula tatasusunan terkumpul menjadi tatasusunan baharu untuk diisih.
  5. Ulang langkah 3 dan 4 sehingga semua digit telah dibandingkan.

Contoh kod:
Berikut ialah contoh kod algoritma isihan radix yang ditulis dalam 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 + " ");
        }
    }
}
Salin selepas log masuk

Hasil berjalan:

Before sorting:
170 45 75 90 802 24 2 66 

After sorting:
2 24 45 66 75 90 170 802
Salin selepas log masuk

Ringkasan:
Algoritma isihan radix ialah algoritma pengisihan yang agak cekap yang boleh melakukan operasi pada integer tatasusunan Isih pantas. Dengan mengisih tatasusunan untuk diisih dari rendah ke tinggi, tatasusunan tertib akhirnya diperolehi. Apabila menggunakan C# untuk menulis algoritma pengisihan radix, kita perlu terlebih dahulu mencari nilai maksimum dan bilangan digit tatasusunan yang hendak diisih, kemudian mengira dan mengisih setiap digit, dan akhirnya menggabungkan semula tatasusunan yang diisih untuk mendapatkan hasil tersusun. Seperti yang dapat dilihat daripada hasil larian kod sampel, algoritma isihan radix boleh mengisih tatasusunan dengan betul.

Atas ialah kandungan terperinci Bagaimana untuk menulis algoritma isihan radix menggunakan C#. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Label berkaitan:
sumber:php.cn
Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan
Tentang kita Penafian Sitemap
Laman web PHP Cina:Latihan PHP dalam talian kebajikan awam,Bantu pelajar PHP berkembang dengan cepat!