算法八：基数排序（O(d*(n+k))）

 

基数排序是按照要排序数字的从低到高位，依次循环排序，其中每位数字的排序算法要是稳定的算法。

 

如下图所示的，7个3位数排序步骤如下：

329                 720                 720                 329

457                 355                 329                 355

657                 436                 436                 436

839   ——>    457   ——>   839   ——>    457

436                 657                 355                 657

720                 329                 457                 720

355                 839                 657                 839

 

算法的伪代码如下：

radix_sort(A, d)

1 for i in 1 to d

2          do use a stable sort to sort array A on digit i

 

引理1：给定n个d位数，每一个数位可以取k种可能的值。如果所用的稳定排序需要O(n+k)的时间，基数排序算法的时间则为O(d*(n+k))。

 

引理2：给定n个b位数，设任意的一个正整数r<=b，基数排序的算法时间复杂度为O((b/r)*(n+2^r))。 

注释：b位数指一共有b位的二进制数。