0.033秒的艺术 ---- Radix Sort
仅供个人学习使用，请勿转载，勿用于任何商业用途。
之前的一篇文章里，讨论过关于快速排序的问题，最近又研究了一下各种排序算法，无意间看到Radix Sort，测试了一下猜猜结果如何？借用GameDev上一位老兄的话说“fast like hell”!
Radix Sort(基排序)可以说是最被人们忽视的排序算法，学校里讲排序时通常只会提到几种出名的比较排序方法，连算法导论也只是稍稍提了一下，没有给出具体实现步骤。这里有关于radix sort的具体算法，原理应该比quick sort还简单，这里有C++版本的实现代码，同样非常简洁，以下是C#版：
private Int64[] tempArray;
private int[] count = new int[256];
private int[] offsetTable = new int[256];
public void RadixSort()
{
Radix(0, array, tempArray);
Radix(1, tempArray, array);
Radix(2, array, tempArray);
Radix(3, tempArray, array);
Radix(4, array, tempArray);
Radix(5, tempArray, array);
Radix(6, array, tempArray);
Radix(7, tempArray, array);
}
private void Radix(int byteIndex, Int64[] source, Int64[] dest)
{
Array.Clear(count, 0, 256);
int byteOffset = byteIndex * 8;
for (int i = 0; i < elementCount; i++)
{
byte radixValue = (byte)(source[i] >> byteOffset);
count[radixValue]++;
}
offsetTable[0] = 0;
for (int i = 1; i < 256; i++)
{
offsetTable[i] = offsetTable[i - 1] + count[i - 1];
}
for (int i = 0; i < elementCount; i++)
{
int index = offsetTable[(byte)(source[i] >> byteOffset]++;
dest[index] = source[i];
}
}
当然，radix sort也并不是没有缺点，首先，待排序的值最好是整数；其次，需要占用额外的内存，而大多数比较排序算法都可以原地排序；最后，待排数据量最好在10k以下(对于不同的硬件，这个值有可能变化)。
下面是用Q6600(2.4G,4 core)对Int64进行排序得出的结果：
quick sort radix sort
1k 1ms 0ms
2k 1ms 0ms
5k 2ms 1ms
10k 4ms 2ms
50k 18ms 13ms
100k 38ms 35ms
500k 212ms 654ms
可以看到对于10k以下的数据量，radix sort优势非常明显，特别是2k以下时，已经快到无法正确测出时间了。注意，这里用的是Int64，对radix sort来说，需要用8个pass完成排序，对Int32来说，则只要4个pass，理论上速度还会快一倍。不幸的是当数据量曾大时，radix sort性能出现了戏剧性的变化，没有做具体分析，但猜想应该是受CPU缓存大小影响的原因。我在另外一台非常古老的P4 2.4(L2 512k)机器上做测试，数据大于10k时，radix sort的优势就不太明显了。
结论：对于大部分游戏来说，渲染队列的数量都不会超过10k，通常在2～3k左右，因此，尝试使用radix sort来进行排序是非常值得的。