C# 基数排序

最后修改于 2025年3月8日

本教程使用 C# 实现并解释基数排序算法，重点在于高效地排序数字和文本数据。

算法是为了解决问题或执行任务而精心设计的精确步骤序列。它是编程的核心概念，驱动着计算解决方案。

排序涉及将数据排列成定义的顺序，例如升序或降序。它可以提高数据访问速度并支持搜索等应用程序中的分析。

常用排序算法

以下是一些著名的排序算法

气泡排序
选择排序
插入排序
归并排序
快速排序
基数排序

基数排序

基数排序是一种非比较算法，它通过处理数据的每个数字或字符进行排序，从最低有效位到最高有效位。它擅长处理整数和固定长度的字符串。

与基于比较的排序（如快速排序）不同，基数排序使用计数将元素分配到桶中，在特定条件下提供线性时间复杂度。

基数排序示例

这是一个使用顶级语句实现的 C# 整数基数排序的例子。

RadixSort.cs

// RadixSort.cs
void CountingSort(int[] arr, int exp)
{
    int n = arr.Length;
    int[] output = new int[n];
    int[] count = new int[10];

    for (int i = 0; i < n; i++)
    {
        int index = arr[i] / exp;
        count[index % 10]++;
    }

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

    for (int i = n - 1; i >= 0; i--)
    {
        int index = arr[i] / exp;
        output[count[index % 10] - 1] = arr[i];
        count[index % 10]--;
    }

    for (int i = 0; i < n; i++)
    {
        arr[i] = output[i];
    }
}

void RadixSort(int[] arr)
{
    int maxNum = arr.Max();
    for (int exp = 1; maxNum / exp > 0; exp *= 10)
    {
        CountingSort(arr, exp);
    }
}

int[] arr = [170, 45, 75, 90, 802, 24, 2, 66];
RadixSort(arr);
Console.WriteLine("Sorted array: " + string.Join(" ", arr));

此代码使用 CountingSort 作为助手来按每个数字进行排序，从最低有效位开始。 exp 变量跟踪当前数字位 (1, 10, 100 等)。

RadixSort 方法查找最大数字以确定要处理的位数。它就地修改数组，高效地按升序对其进行排序。

对文本数据进行排序

基数排序也可以对字符串进行排序。下面是一个对字符串进行升序和降序排序的示例。

RadixSortStrings.cs

// RadixSortStrings.cs
void CountingSortStrings(string[] arr, int index)
{
    int n = arr.Length;
    string[] output = new string[n];
    int[] count = new int[256];

    for (int i = 0; i < n; i++)
    {
        byte charVal = 0;
        if (index < arr[i].Length)
        {
            charVal = (byte)arr[i][index];
        }
        count[charVal]++;
    }

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

    for (int i = n - 1; i >= 0; i--)
    {
        byte charVal = 0;
        if (index < arr[i].Length)
        {
            charVal = (byte)arr[i][index];
        }
        output[count[charVal] - 1] = arr[i];
        count[charVal]--;
    }

    for (int i = 0; i < n; i++)
    {
        arr[i] = output[i];
    }
}

void RadixSortStrings(string[] arr, bool reverse)
{
    int maxLen = arr.Max(s => s.Length);
    for (int i = maxLen - 1; i >= 0; i--)
    {
        CountingSortStrings(arr, i);
    }
    if (reverse)
    {
        for (int i = 0, j = arr.Length - 1; i < j; i++, j--)
        {
            (arr[i], arr[j]) = (arr[j], arr[i]);
        }
    }
}

string[] arr = ["apple", "banana", "kiwi", "mango", "cherry"];
RadixSortStrings(arr, false);
Console.WriteLine("Ascending order: " + string.Join(" ", arr));

RadixSortStrings(arr, true);
Console.WriteLine("Descending order: " + string.Join(" ", arr));

CountingSortStrings 方法基于特定的字符位置进行排序，使用 256 个槽的计数数组来存储 ASCII 字符。它隐式地用空字节填充较短的字符串。

RadixSortStrings 方法从右到左处理字符，确保正确的字典顺序。 reverse 标志在排序后交换元素以实现降序。

这在 C# 应用程序中需要文本数据组织时，对于排序名称、ID 或标签非常实用。

基数排序与快速排序的比较

基数排序在固定大小的数据（如整数或字符串）中表现出色，其时间复杂度为 O(nk)，其中 k 是数字或字符的数量。快速排序的平均复杂度为 O(n log n)，用途更广泛。

下面的基准测试比较了它们在 C# 中大型整数数据集上的性能，突出了它们的优势。

RadixVsQuick.cs

// RadixVsQuick.cs
using System.Diagnostics;

void CountingSort(int[] arr, int exp)
{
    int n = arr.Length;
    int[] output = new int[n];
    int[] count = new int[10];

    for (int i = 0; i < n; i++)
    {
        int index = arr[i] / exp;
        count[index % 10]++;
    }

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

    for (int i = n - 1; i >= 0; i--)
    {
        int index = arr[i] / exp;
        output[count[index % 10] - 1] = arr[i];
        count[index % 10]--;
    }

    for (int i = 0; i < n; i++)
    {
        arr[i] = output[i];
    }
}

void RadixSort(int[] arr)
{
    int maxNum = arr.Max();
    for (int exp = 1; maxNum / exp > 0; exp *= 10)
    {
        CountingSort(arr, exp);
    }
}

int[] QuickSort(int[] arr)
{
    if (arr.Length <= 1)
    {
        return arr;
    }
    int pivot = arr[arr.Length / 2];
    var left = new List<int>();
    var middle = new List<int>();
    var right = new List<int>();

    foreach (int x in arr)
    {
        if (x < pivot)
        {
            left.Add(x);
        }
        else if (x == pivot)
        {
            middle.Add(x);
        }
        else
        {
            right.Add(x);
        }
    }

    return [.. QuickSort(left.ToArray()), .. middle, .. QuickSort(right.ToArray())];
}

Random rand = new(Random.Shared.Next());
int[] arr = new int[10000];
for (int i = 0; i < arr.Length; i++)
{
    arr[i] = rand.Next(10000);
}

int[] radixData = arr.ToArray();
Stopwatch sw = Stopwatch.StartNew();
RadixSort(radixData);
double radixTime = sw.Elapsed.TotalSeconds;

int[] quickData = arr.ToArray();
sw = Stopwatch.StartNew();
QuickSort(quickData);
double quickTime = sw.Elapsed.TotalSeconds;

Console.WriteLine($"Radix Sort time: {radixTime:F6} seconds");
Console.WriteLine($"Quick Sort time: {quickTime:F6} seconds");

此基准测试创建了 10,000 个随机整数。 RadixSort 使用基于数字的计数进行原地排序，而 QuickSort 递归地对数据进行分区，并返回一个新数组。

对于具有小范围数字的整数，基数排序通常优于快速排序，但快速排序更适应各种数据类型。结果各不相同，但在此数据集上，基数排序通常略胜一筹。

来源

C# Array.Sort 文档

本教程使用 C# 实现了基数排序，涵盖数字和字符串，并与快速排序进行了性能比较。

作者

我的名字是 Jan Bodnar，我是一位充满激情的程序员，拥有多年的编程经验。我自 2007 年以来一直在撰写编程文章。

到目前为止，我已经撰写了 1400 多篇文章和 8 本电子书。我拥有超过八年的编程教学经验。

列出所有 C# 教程。