Wandai Blog 共被围观 1,640,254 次

(1)设计大数单位

我觉得用科学记数法就好~

(2)设计比冒泡排序O(n^2)好的排序算法, 支持任意对象

假设: 内存无限大, Integer能存无限大的数

首先我们需要有一个函数Integer f(Object x), 该函数接受任意实现了比大小的接口的对象, 它返回一个整数(对于不同的x有不同的函数值), 若x1>x2则f(x1)>f(x2)。

如: 对于x是任意数字对象则可以有f(x)=x。

然后我们只需要两个大数组记为Integer[] C和Object[] O。

对于每个输入的x, 执行O[f(x)]=x;/*这是便于以后用f(x)来反查x*/ C[f(x)]++;/*计数器*/ max_v=f(x)>max_v?f(x):max_v; min_v=f(x)<min_v?f(x):min_v; /*这两个是用来记录下一步要扫描的范围*/

然后需要类似于vector的东西记为vector<Object> V。

然后只要扫描一遍C[i=min_v->max_v],

for j=1->C[i] : V.push_back(O[i]);

V中内容即为所求。

据说是O(n)的算法!

(只是为了写作业~)