基数排序

假设对0~10^6-1的1000个整数进行排序，使用基数排序r=10^6的排序方法相当于直接对数使用箱子排序。对箱子的初始化需要10^6个执行步，节点分配需要1000个执行步，收集箱子节点需要10^6个执行步，总的执行步数为2001000。 使用基数r=1000的排序方法，其过程如下： （1）采用每个数的最低3位数字进行排序，令range=1000； （2）对（1）的结果按倒数次3位（即倒数第4到第6位）数字进行排序。 上述每次排序都需要3000个执行步，因此总共需要6000步。若使用基数为r=100的排序方法，则需要三次箱子排序，每次针对两位数字。每次箱子排序需要1200个执行步，总的执行步数为3600.如果使用基数为r=10的排序方法，则要进行6次箱子排序，每次针对一位数字，总的执行步骤数为6*(10+1000+10)=6120.对于本例，基数r=100的排序效率最高。 把数分解为数字需要除法和取模操作。如果用基数10来分解，那么从最低位到最高位的数字分解式为： x%10； (x%100)/10； (x%1000)/100； …… 若r=100，则相应的数字分解式为： x%100； (x%10000)/100； (x%1000000)/10000； …… 对于一般的基数r，相应的分解式为： x%r； (x%r^2)/r； (x%r^3)/r^2; …… 当使用基数r=n对0~n^c-1范围内的n个整数进行分解时，每个数可以分解出c个数字。因此，对n个数，可以用c次range=n个箱子排序。因为c是一个常量，所以整个排序时间为O(cn)=O(n)。