我觉得基数排序的复杂度是d*n*logN啊,为什么书上说是O(d(n+k))呢?
《算法导论》的第8章介绍基数(radix)排序，有n个d位数，每一位有k种取值，排序的复杂度是O(d(n+k))。
-----------------------------------------------------
但是我觉得，每一位，例如最低位要排序的话，就需要n*nlogN的算法复杂度，整体就是d*n*longN
为什么书上说每一位的排序需要O(n+k)呢?
这就好比，我有一个简单的数组{1,9,4,2,7,5,8}，对它进行排序我觉得总是n*logN啊，O(n+k)是怎么来的?
[解决办法]
最低位排序是直接建d个桶，把元素按照最低位插入对应桶末尾，然后再把桶接起来。这样做一位只需要O(n+k)。
你的例子里，那就是建10个桶，然后1,9,4,2,7,5,8放到这10个桶里的对应的桶，然后再把10个桶按照0~9的顺序取数。当年你的例子d=1，拿来理解整个算法不怎么适合。用个3位数的数组去理解比较好。
[解决办法]
你把红色部分搞错了，基数排序是以计数排序为基础的，所以是线性的
（ 虽然计数排序是稳定的，但是实际中测试得：难以保证线性时间，所以算法导论讲这个我个人认为就是开阔视野，然后告诉你：线性不适用 ）
