counting sort an array of objects怎么做 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

counting sort an array of objects怎么做

counting sort an array of objects怎么做# JobHunting - 待字闺中

S*C2015-03-29 07:03

1 楼

10 million的数组，数字是8bit的非负数，排序
count sort搞定
follow up，10 million的item class，item有rating和name，根据rating sort。
rating和上面一样也是8bit unsign.
Amazon intern问题

a*r2015-03-29 07:03

2 楼

实现item class的时候实现一个比较的function -里面根据rating 比较大小。

S*C2015-03-29 07:03

3 楼

这样的话是调用Collections.sort()方法，这个是mergeSort()
时间复杂度是O(NlogN）而不是counting sort 的O(N)

【在 a****r 的大作中提到】

: 实现item class的时候实现一个比较的function -里面根据rating 比较大小。

d*e2015-03-29 07:03

4 楼

8比特开一个256的数组好了
不用调用库函数
第一计数
第二搞一个seq

【在 S*******C 的大作中提到】

: 10 million的数组，数字是8bit的非负数，排序
: count sort搞定
: follow up，10 million的item class，item有rating和name，根据rating sort。
: rating和上面一样也是8bit unsign.
: Amazon intern问题

m*g2015-03-29 07:03

5 楼

两种办法：
1.搞256个链表，rating是x的就放在x号链表里，最后顺序输出各个链表里的object，
如果要求stable的话，要注意插入位置和扫描顺序。
2.简单的计数数组，计完数之后，把计数变换成该rating对象在输出数组中的下一个
index，假设输入有N个object
a[255] = N - a[255];
for (int i = 254; i >= 0; --i) {
a[i] = a[i + 1] - a[i];
}
最后输出时，从前往后扫输入数组，rating为x的，放在输出数组的a[x]位置，然后+
+a[x]。这个屏记忆写的，不保证完全正确，建议查一下CRLS。