如何高效生成按学生平均分升序指向原二进制文件位置的索引文件

核心前提 #

现有约束为：不可修改原有student结构体定义，所有学生数据已全部读取至结构体数组中，需生成按学生平均分升序排列的原二进制文件偏移索引文件。

实现步骤 #

• 第一步：生成偏移映射临时数组
  读取原二进制文件的过程中，每成功读取一个学生结构体并存入目标数组的第i个位置时，同步向临时数组插入一条二元组记录 (i, 当前学生数据在原文件的起始偏移量)，该步骤时间复杂度为O(X)，不会对原结构体数组产生任何修改。
• 第二步：对临时数组做自定义规则排序
  不对原学生结构体数组做任何排序操作，仅对上述临时数组执行排序，排序的比较规则为：取临时数组元素中存储的下标i，对应访问 students[i].average 平均分，按平均分升序排列临时数组元素。排序逻辑可直接使用你熟悉的归并排序，仅需调整比较逻辑的取值来源即可，时间复杂度为O(X log X)，和常规排序效率一致。
• 第三步：直接生成索引文件
  临时数组排序完成后，按顺序将每条记录中的原文件起始偏移量字段依次写入索引文件即可，该步骤时间复杂度为O(X)。

方案优势 #

• 完全符合约束：不需要修改原有student结构体的任何定义，仅新增的临时数组内存占用极低（单条记录仅存2个int值，100万条数据仅占用约8MB内存）
• 无需改动原学生数组的任何数据或顺序，不会影响原有逻辑对学生数组的使用
• 整体效率最优，无任何冗余计算，排序逻辑可复用现有成熟实现，落地成本极低

内容的提问来源于stack exchange，提问作者thatDude