2 fanfusuzi2008123 fanfusuzi2008123 于 2015.06.14 13:34 提问

一道面试题(关于千万量级数据结构排序)

题目:
已知文件中存有全国英语六级历年来的成绩(千万级别,考生分数都是正整数,最高710分),每一行都是一个人的姓名、考号和成绩,请你对考生的成绩从高到低进行排序,输出到另一个文件中。
格式 如下:
李四,201008823,678;
张三,201007432,356;
王五,201322233,464;
排序后:
李四,201008823,678;
王五,201322233,464;
王五,201322233,464;
要求:使空间复杂度和时间复杂度尽可能低,希望可以达到时间复杂度为O(n)。按目前数据量预计计算机内存足够。可以用伪代码或说明思路
刚注册,没有分可悬赏,但应该是个不错的题。。

    以下是我的思路,但是不能完全解答出来,请高手提提建议:
    1.首先这个排序的依据是分数,而英语四级考试分数有范围0-710分。题目希望时间复杂度尽可能低。排除依据比较的排序算法如快速排序、选择排序,应该选择线性排序算法。
    2.再因为是千万级的数据,可以考虑使用桶排序,建立一个有711大小的桶(数组),遍历整个文档,根据分数大小在相应的桶号上计数。
    3.根据上面两步,基本是可以实现单纯的成绩排序。而且时间复杂度为O(n),空间复杂度也就是多一个桶数组。
    4.困难:问题是,基于计数的桶排序的对象如果是纯数字,好说。但是题目是带有姓名、考号和成绩三个属性的对象。怎么利用桶排序呢?

    谢谢!

5个回答

91program
91program   Ds   Rxr 2015.06.14 15:36

刚注册,没有分可悬赏,这个不是问题!可以充值的,充了就有悬赏的C币,不是分!

fanfusuzi2008123
fanfusuzi2008123 回复91program: 哦。啥样的结构体?是键值对吗?能说的稍微细点不?谢谢
2 年多之前 回复
91program
91program 将每一行数的行数与分数一起做一个简单的结构体,按分数排序、按行数取完整的数据。
2 年多之前 回复
weixin_29018649
weixin_29018649   2015.06.14 13:56

文件读写么,定义一个类型为struct的vestor容器,你把数据读到struct里面,然后把成绩取出来不就完了

CodeofWorker
CodeofWorker   2015.06.14 14:16

其实这道题是单希望使用单循环即O(n),这个关键字在于分数,其实就是按分数做个最优的排序,是否不用想得太深呢?
只要想的是怎么实现单循环排序。

CodeofWorker
CodeofWorker 回复fanfusuzi2008123: http://blog.csdn.net/xiazdong/article/details/8462393我菜鸟,给你这个
2 年多之前 回复
fanfusuzi2008123
fanfusuzi2008123 那你认为最优的单循环排序是啥呢?
2 年多之前 回复
zhi_ai_yaya
zhi_ai_yaya   Rxr 2015.06.15 09:19

对于排序,并不一定要使用基本类型。
#基于C++
首先要理解排序算法模型:它是通过数据和排序函数进行排序的。应该可以自定义Student类,然后在类中重载比较函数,把比较函数作为排序函数传给排序控制器。因为比较函数并不复杂,可以做成内联函数,避免递归调用。
因为只是对成绩排名,不需要再对学号排名,而且成绩范围确定[0-710],所以桶排序应该没问题。

Anne999
Anne999   2015.06.15 15:59

数据结构存储是让姓名与学号关联,学号与成绩关联,只对学号与成绩那组进行排序,时间复杂度中空间复杂度好。
struct std1
{
char name[10];
int number[10];
};
struct std2
{
int chengji;
int number[10];
}
对第二个进行排序,可以吗?

Csdn user default icon
上传中...
上传图片
插入图片