问题描述

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

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

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

    谢谢！

解决方案

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

解决方案二：

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

解决方案三：

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

解决方案四：

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

解决方案五：

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