如何使用C#寫基數排序演算法
引言：
基數排序（Radix Sort）是一種非比較型的排序演算法，適用於對整數進行排序。它的基本思想是將待排序的元素依照低位到高位的順序依序排序，從而得到有序序列。相對於其他排序演算法，基數排序的時間複雜度較低，且具有穩定性。
實作步驟：
程式碼範例：
以下是使用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 + " ");
}
}
}執行結果：
Before sorting: 170 45 75 90 802 24 2 66 After sorting: 2 24 45 66 75 90 170 802
總結：
基數排序演算法是一種效率較高的排序演算法，能夠對整數陣列進行快速排序。透過將待排序數組依照位數從低到高排序，最終得到有序的數組。使用C#寫基數排序演算法時，我們需要先找出待排序數組的最大值和位數，然後按照每一位進行計數排序，最後將排序後的數組重新組合得到有序結果。透過範例程式碼的運行結果可以看到，基數排序演算法能夠正確地對數組進行排序。
以上是如何使用C#寫基數排序演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！
