算法

w25

看到一到关于排序的考试题
show how to sort n integers in the range 0 to n*n-1 in O(n) time.

在0到n方-1的这n方个数中选择n个数（无序），怎样排序才能使排序的时间复杂度为O(n).

thank you for your replay!

w25

在存储位置和关键字之间建立一一对应关系的方法我到是想过，的确可行，不过这道题只在百分之中只值5分，所以是不是有些其他的方法，我正在想...感谢你的回答！

win_hate

原帖由 "w25" 发表：
看到一到关于排序的考试题
show how to sort n integers in the range 0 to n*n-1 in O(n) time.

在0到n方-1的这n方个数中选择n个数（无序），怎样排序才能使排序的时间复杂度为O(n).

thank you for your rep..........

用 "基数排序", 查 数据结构 的书.

w25

基数排序我没想过，我先是找时间复杂度为O(n)的排序方法，一看技术排序的复杂度为o(n*d),我就放弃了。我总觉得该题的数在0到n方-1中出有一定目的，要不为什么不从0到n-1中出，直接排这n个数就的了。看来就用基数排序写程序了。thank you

win_hate

[quote]原帖由 "w25"]基数排序我没想过，我先是找时间复杂度为O(n)的排序方法，一看技术排序的复杂度为o(n*d),我就放弃了。我总觉得该题的数在0到n方-1中出有一定目的，要不为什么不从0到n-1中出，直接排这n个数就的了。看来就用基数排序..........[/quote 发表：


一般假设 d 是一个常数,  所以 O(n*d) 就是  O(n)

比如: O( 1024 n)=O(2n) = O(n)

w25

thank you ,刚才我用基数链表的思路写程序实现这个算法，写道一半多的时候就有种后悔的感觉，倒不是程序无法实现，就是感觉用基数排序还不如哈希表排序，虽然说哈希表在空间上的花销大了一点点，但基数排序光申请每趟的指针就让我的脑袋疼得够呛，两趟需要20个啊（是不是我定义n为10大了些，哈哈）。

win_hate

n=10 太小了. 基数排序要很多辅助的工作, 只有 n 很大的时候才有优势.

比如; n=2^8, n^2 = 2^16

在这 2^16 = 65526 以下随便选 256 个数, 注意到这些数的长度不超过16位. 你可以把这些数拆分为 2 个字节, 利用这两个字节进行基数排序(基为 2^8) 两趟就搞定了.

如果每趟的工作量仍然太大, 可以拆为4个半字节, 4 趟完成.