有没有现成的基数排序实现可以用于C#？

Question

最好使用任何非病毒开源许可证

- skevar7

---

“非病毒开源许可证”是什么意思？ - abatishchev

Answer 1

这里有一个来自维基教科书的排序算法（基于最低有效位）。

public void RadixSort(int[] a)
{  
    // our helper array 
    int[] t=new int[a.Length]; 

    // number of bits our group will be long 
    int r=4; // try to set this also to 2, 8 or 16 to see if it is 
             // quicker or not 

    // number of bits of a C# int 
    int b=32; 

    // counting and prefix arrays
    // (note dimensions 2^r which is the number of all possible values of a 
    // r-bit number) 
    int[] count=new int[1<<r]; 
    int[] pref=new int[1<<r]; 

    // number of groups 
    int groups=(int)Math.Ceiling((double)b/(double)r); 

    // the mask to identify groups 
    int mask = (1<<r)-1; 

    // the algorithm: 
    for (int c=0, shift=0; c<groups; c++, shift+=r)
    { 
        // reset count array 
        for (int j=0; j<count.Length; j++)
            count[j]=0;

        // counting elements of the c-th group 
        for (int i=0; i<a.Length; i++)
            count[(a[i]>>shift)&mask]++; 

        // calculating prefixes 
        pref[0]=0; 
        for (int i=1; i<count.Length; i++)
            pref[i]=pref[i-1]+count[i-1]; 

        // from a[] to t[] elements ordered by c-th group 
        for (int i=0; i<a.Length; i++)
            t[pref[(a[i]>>shift)&mask]++]=a[i]; 

        // a[]=t[] and start again until the last group 
        t.CopyTo(a,0); 
    } 
    // a is sorted 
}

- TheVillageIdiot

---

哦，count[(a[i]>>shift)&mask]++; 真是太易读了！ - abatishchev

@abatishchev 请编辑更易读的版本。 - TheVillageIdiot

这不是对你回答的评论，而是针对那篇维基百科文章的。一本学习算法的书中包含了几乎无法阅读和理解的代码（只是说一下）。 - abatishchev

@abatishchev，说实话，乍一看它很易读懂。对我来说...它只是表明您想要增加所需组的计数器。变量 shift 是掩码的大小，因此您基本上是通过将掩码移动到数字中并以此方式获取组 ID。 - Mladen B.

我在这里找到了一个更易读的例子：https://www.w3resource.com/csharp-exercises/searching-and-sorting-algorithm/searching-and-sorting-algorithm-exercise-10.php，与使用常量32不同，此例子使用31和-1作为边界。 这个例子也更加清晰，循环次数更少。 - dyslexicanaboko

@ Mladen B，你真是个聪明的人，做得很好。这看起来像是有人将C版本直接移植到了C#上。使用所有这些位移操作，看起来代码最初是为70年代的C编译器编写的，而不是2021年的C#编译器。如果不明白为什么这样做不好，请查看Eric Lippert在此处的回答：https://dev59.com/cHA75IYBdhLWcg3w3NLf - Ash

Answer 2

    public static int[] radixSort(int[] ar)
    {
        int width = 0;
        foreach (int el in ar)
        {
            int numDigits = el.ToString().Length;
            if (numDigits > width)
                width = numDigits;
        }

        int md, n;

        Dictionary<int, LinkedList> queue = null;

        Action refreshQueue = () =>
       {
           queue = new Dictionary<int, LinkedList>();

           for (int i = 0; i <= 9; i++)
           {
               queue[i] = null;
           }
       };

        refreshQueue();

        for (int i = 1; i <= width; i++)
        {
            md = (int)Math.Pow(10, i); 
            n = md / 10; 

            foreach (int el in ar)
            {
                int ithPlace = (int)((el % md) / n);
                if (queue[ithPlace] == null)
                    queue[ithPlace] = new LinkedList(new LinkedListNode(el));
                else
                    queue[ithPlace].add(new LinkedListNode(el));
            }

            List<int> newArray = new List<int>();
            for (int k = 0; k <= 9; k++)
            {
                if (queue[k] != null)
                {
                    LinkedListNode head = queue[k].head;
                    while (head != null)
                    {
                        newArray.Add(head.value);
                        head = head.next;
                    }
                }
            }
            ar = newArray.ToArray();
            refreshQueue();
        }

        return ar;
    }

- Lee.O.