somebody0101 2015-06-14 05:34 采纳率: 0%
浏览 1998

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

题目:
已知文件中存有全国英语六级历年来的成绩(千万级别,考生分数都是正整数,最高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条回答 默认 最新

  • CodeofWorker 2015-06-14 06:16
    关注

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

    评论

报告相同问题?

悬赏问题

  • ¥15 多电路系统共用电源的串扰问题
  • ¥15 slam rangenet++配置
  • ¥15 有没有研究水声通信方面的帮我改俩matlab代码
  • ¥15 对于相关问题的求解与代码
  • ¥15 ubuntu子系统密码忘记
  • ¥15 信号傅里叶变换在matlab上遇到的小问题请求帮助
  • ¥15 保护模式-系统加载-段寄存器
  • ¥15 电脑桌面设定一个区域禁止鼠标操作
  • ¥15 求NPF226060磁芯的详细资料
  • ¥15 使用R语言marginaleffects包进行边际效应图绘制