2012计算机大纲新增外部排序解析

"2012年计算机考研大纲新增及改动的知识点，主要涉及数据结构中的外部排序部分。" 2012年计算机考研大纲的更新主要集中在数据结构的排序章节，特别是对外部排序进行了补充。外部排序是处理大规模数据时，由于数据量过大无法一次性装入内存而采用的一种特殊的排序方法。在2012年的大纲中，这一部分被列为了解型知识点，意味着考生需要理解外部排序的基本概念和方法，但可能不会深入到算法设计层面进行考核。 1. 外部排序的基本概念： - 外部排序是指当待排序的数据量过大，无法全部装入内存，需要借助外部存储设备进行排序的情况。在这种情况下，数据需要分批调入内存进行排序，然后将结果写回外部存储，整个过程涉及到多次内存与外存的交互。 2. 外部排序的方法： - 通常分为两类：磁盘文件排序和磁带文件排序。这两种方法主要区别在于初始归并段在外存的分布方式，磁盘支持随机访问，而磁带则只能顺序访问。 - 在外部排序中，由于磁盘读写操作的时间远大于内存运算，因此优化的关键在于减少I/O操作次数，这是衡量外部排序效率的重要指标。 3. 外部排序的步骤： - 外部排序通常采用多路归并排序策略，它包含两个主要阶段：首先是归并排序的预处理阶段，将大文件分割成多个小的、可以一次性装入内存的子文件（称为归并段）；其次是多路平衡归并阶段，将这些子文件逐步合并成一个有序的大文件。 4. 优化技术： - 为了减少I/O次数，可以采用增大归并路数（如利用败者树）或减少归并段个数（如置换-选择排序）的方法。 - 对于长度不等的归并段，构建最佳归并树是实现高效归并的关键，以确保每次合并时能平衡数据读写。 大纲中特别指出，外部排序在本科课程中可能被略过，而且外部排序与内部排序的比较并非重点，因此考生在复习时不必过于纠结这部分内容的细节。尽管如此，理解外部排序的基本原理和方法对于全面掌握数据结构知识仍然是有益的，特别是在面对大数据处理问题时。