Jede fertige Implementierung von Radix Sort for C#?

Question

Vorzugsweise mit jedem Nicht-Virus Open-Source-Lizenz

Answer 1

hier ist ein von wikibooks (Dies ist Least Significant Digit basiert)

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 
} 

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; 
    }