C#排序算法新境界：深度剖析与高效实现基数排序

基数排序（Radix Sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数进行比较。具体来说，基数排序有两种方法：

1. 最低位优先（LSD, Least Significant Digit first）：从最低位开始，向最高位进行排序。
2. 最高位优先（MSD, Most Significant Digit first）：通常用于字符串的排序，从最高位开始，向最低位进行排序，且常使用递归实现。

在这里，我们将以最低位优先（LSD）的方式实现一个针对非负整数的基数排序。为了简化，我们假设所有整数都是非负的，并且它们的位数都是相同的（或者我们可以对它们进行补零以使得位数相同）。

以下是基数排序的C#实现：

using System;
using System.Collections.Generic;class Program
{static void Main(string[] args){int[] arr = { 170, 45, 75, 90, 802, 24, 2, 66 };​// 调用基数排序RadixSort(arr);
​Console.WriteLine("Sorted array: ");foreach (int num in arr){Console.Write(num + " ");}Console.WriteLine();}​// 基数排序方法static void RadixSort(int[] arr){// 找到数组中的最大值以确定最大位数int max = arr[0];for (int i = 1; i < arr.Length; i++){if (arr[i] > max)max = arr[i];}
​// 对每个位数进行排序for (int exp = 1; max / exp > 0; exp *= 10){CountingSortForRadix(arr, exp);}}​// 基数排序中的计数排序，用于按当前位数排序static void CountingSortForRadix(int[] arr, int exp){int n = arr.Length;int[] output = new int[n]; // 输出数组    int[] count = new int[10]; // 计数数组，0-9
​// 存储当前位的值for (var i = 0; i < n; i++)count[(arr[i] / exp) % 10]++;
​// 更改count[i]，使其包含实际的位置信息for (var i = 1; i < 10; i++)count[i] += count[i - 1];
​// 构建输出数组for (var i = n - 1; i >= 0; i--){output[count[(arr[i] / exp) % 10] - 1] = arr[i];count[(arr[i] / exp) % 10]--;}​// 将排序后的数据复制回原数组for (var i = 0; i < n; i++)arr[i] = output[i];}
}
​

在这个实现中，RadixSort 方法首先找到数组中的最大值，以确定需要处理的最大位数。然后，它使用一个循环，每次循环对当前位（从最低位开始）进行排序。

CountingSortForRadix 方法是一个辅助方法，它使用计数排序来对数组中的元素按当前位进行排序。这个方法首先计算每个数字在当前位上的值（通过除以当前位的位权并取模10得到），然后使用一个计数数组来记录每个值出现的次数。接下来，它修改计数数组，使得每个位置包含小于或等于当前值的元素应该占据的位置。最后，它使用这些信息来构建排序后的数组，并将其复制回原数组。

注意，这个实现假设了所有数字都是非负的，并且它们的位数可能不同（通过最高位之前的0来隐含地表示较短的数字）。如果输入包含负数，或者你需要对字符串进行排序，你可能需要修改这个算法以适应这些情况。