首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

单链表C#中的基数排序

单链表是一种常见的数据结构,它由一系列节点组成,每个节点包含一个数据元素和一个指向下一个节点的指针。基数排序是一种非比较排序算法,它根据元素的位值将元素分配到不同的桶中,然后按照桶的顺序依次收集元素,最终得到有序的结果。

在C#中实现单链表可以使用自定义的节点类和链表类。节点类可以定义如下:

代码语言:txt
复制
public class ListNode
{
    public int Value { get; set; }
    public ListNode Next { get; set; }

    public ListNode(int value)
    {
        Value = value;
        Next = null;
    }
}

链表类可以定义如下:

代码语言:txt
复制
public class LinkedList
{
    private ListNode head;

    public LinkedList()
    {
        head = null;
    }

    public void Add(int value)
    {
        ListNode newNode = new ListNode(value);
        if (head == null)
        {
            head = newNode;
        }
        else
        {
            ListNode current = head;
            while (current.Next != null)
            {
                current = current.Next;
            }
            current.Next = newNode;
        }
    }

    public void Print()
    {
        ListNode current = head;
        while (current != null)
        {
            Console.Write(current.Value + " ");
            current = current.Next;
        }
        Console.WriteLine();
    }

    // 基数排序
    public void RadixSort()
    {
        if (head == null || head.Next == null)
        {
            return;
        }

        int maxDigit = GetMaxDigit();
        for (int i = 1; i <= maxDigit; i++)
        {
            ListNode[] buckets = new ListNode[10];
            ListNode current = head;
            while (current != null)
            {
                int digit = GetDigit(current.Value, i);
                if (buckets[digit] == null)
                {
                    buckets[digit] = current;
                }
                else
                {
                    ListNode tail = buckets[digit];
                    while (tail.Next != null)
                    {
                        tail = tail.Next;
                    }
                    tail.Next = current;
                }
                current = current.Next;
            }

            head = null;
            ListNode last = null;
            for (int j = 0; j < 10; j++)
            {
                if (buckets[j] != null)
                {
                    if (head == null)
                    {
                        head = buckets[j];
                    }
                    else
                    {
                        last.Next = buckets[j];
                    }
                    last = GetTail(buckets[j]);
                }
            }
            last.Next = null;
        }
    }

    // 获取链表中的最大位数
    private int GetMaxDigit()
    {
        int maxDigit = 0;
        ListNode current = head;
        while (current != null)
        {
            int digit = GetDigitCount(current.Value);
            if (digit > maxDigit)
            {
                maxDigit = digit;
            }
            current = current.Next;
        }
        return maxDigit;
    }

    // 获取一个数的指定位数上的数字
    private int GetDigit(int number, int digit)
    {
        return (number / (int)Math.Pow(10, digit - 1)) % 10;
    }

    // 获取一个数的位数
    private int GetDigitCount(int number)
    {
        if (number == 0)
        {
            return 1;
        }
        return (int)Math.Floor(Math.Log10(Math.Abs(number)) + 1);
    }

    // 获取链表的尾节点
    private ListNode GetTail(ListNode node)
    {
        ListNode tail = node;
        while (tail.Next != null)
        {
            tail = tail.Next;
        }
        return tail;
    }
}

使用示例:

代码语言:txt
复制
LinkedList list = new LinkedList();
list.Add(170);
list.Add(45);
list.Add(75);
list.Add(90);
list.Add(802);
list.Add(24);
list.Add(2);
list.Add(66);
list.Print(); // 输出:170 45 75 90 802 24 2 66
list.RadixSort();
list.Print(); // 输出:2 24 45 66 75 90 170 802

在腾讯云的产品中,可以使用云服务器(CVM)来进行服务器运维,使用云数据库(CDB)来进行数据库存储,使用云函数(SCF)来进行云原生应用开发,使用云存储(COS)来进行多媒体处理和存储,使用人工智能(AI)服务来进行音视频处理和物联网应用开发,使用区块链(BCBaaS)来构建区块链应用,使用腾讯云元宇宙(Tencent Real-Time Interactive Multimedia Platform,TRIM)来构建元宇宙应用。

相关产品和介绍链接如下:

  • 云服务器(CVM):https://cloud.tencent.com/product/cvm
  • 云数据库(CDB):https://cloud.tencent.com/product/cdb
  • 云函数(SCF):https://cloud.tencent.com/product/scf
  • 云存储(COS):https://cloud.tencent.com/product/cos
  • 人工智能(AI):https://cloud.tencent.com/product/ai
  • 区块链(BCBaaS):https://cloud.tencent.com/product/baas
  • 腾讯云元宇宙(TRIM):https://cloud.tencent.com/product/trim

以上是关于单链表和基数排序的完善且全面的答案,希望能对您有所帮助。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

没有搜到相关的合辑

领券