Preferrably與任何非病毒開源許可任何現成的基數排序實現的C#?
2
A
回答
2
這裏是一個從wikibooks(這是基於最低有效位)
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
}
+0
哦,'count [(a [i] >> shift)&mask] ++;''是如此fk'可讀! – abatishchev
+0
@abatishchev請編輯更可讀的版本。 – TheVillageIdiot
+2
這不是關於你的答案的評論,而是關於那篇wiki文章。一本學習算法的書包含幾乎沒有可讀性和可理解的代碼。只是說) – abatishchev
0
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;
}
相關問題
- 1. 使用C實現基數排序
- 2. C++實現計數排序
- 3. 實現合併排序C++
- 4. 如何改進這種基數排序的實現?
- 5. 拓撲排序的C++實現
- 6. C++中的快速排序實現
- 7. 如何實現冒泡排序在C.
- 8. C#中的基類實現
- 9. SAS中數據集的基數排序實現
- 10. 有關基數排序的Java實現的解釋
- 11. 插入排序的實現
- 12. 任務編排實現
- 13. 如何實現排序類
- 14. 實現堆排序
- 15. 桶排序實現
- 16. 在基於數組的列表上實現選擇排序
- 17. 詞典/ KeyValuePair收集的基數排序實現
- 18. 如何在多GPU上實現基數排序?
- 19. 計數的實現在Python中排序
- 20. 在c#中實現鏈表的排序時出現問題
- 21. C++ 0x的任何實現在那裏?
- 22. 3路快速排序(C實現)
- 23. 問題在C++歸併排序實現
- 24. 在C++中實現合併排序
- 25. 並行快速排序C實現
- 26. 成員函數的不同實現C++
- 27. Objective-C中的關聯數組的實現和排序
- 28. 如何實現特定的排序?
- 29. 基數32 FFT的實現
- 30. C中的堆排序實現 - 數組錯誤
你的意思是「非病毒開源許可」下什麼? – abatishchev