关于外排序算法
要排序的文件大小1G,每个记录长50byte,前5byte是关键码,用什么算法效率最高?
排序问题一般分为内排序( internal sorting )和外排序( external sorting )两类: 1。 内排序:待排序的表中记录个数较少,整个排序过程中所有的记录都可以保留在内存中; 2。 外排序:待排序的记录个数足够多,以至于他们必须存储在磁带、磁盘上组成外部文件,排序过程中需要多次访问外存。
排序算法分析 1.排序算法的基本操作 大多数排序算法都有两个基本的操作: (1) 比较两个关键字的大小; (2) 改变指向记录的指针或移动记录本身。 注意: 第(2)种基本操作的实现依赖于待排序记录的存储方式。
2.待排文件的常用存储方式 (1) 以顺序表(或直接用向量)作为存储结构 排序过程:对记录本身进行物理重排(即通过关键字之间的比较判定,将记录移到合适的位置) (2) 以链表作为存储结构 排序过程:无须移动记录,仅需修改指针。
通常将这类排序称为链表(或链式)排序; (3) 用顺序的方式存储待排序的记录,但同时建立一个辅助表(如包括关键字和指向记录位置的指针组成的索引表) 排序过程:只需对辅助表的表目进行物理重排(即只移动辅助表的表目,而不移动记录本身)。适用于难于在链表上实现,仍需避免排序过程中移动记录的排序方法。
3.排序算法性能评价 (1) 评价排序算法好坏的标准 评价排序算法好坏的标准主要有两条: ① 执行时间和所需的辅助空间 ② 算法本身的复杂程度 (2) 排序算法的空间复杂度 若排序算法所需的辅助空间并不依赖于问题的规模n,即辅助空间是O(1),则称之为就地排序(In-PlaceSou)。
非就地排序一般要求的辅助空间为O(n)。 (3) 排序算法的时间开销 大多数排序算法的时间开销主要是关键字之间的比较和记录的移动。有的排序算法其执行时间不仅依赖于问题的规模,还取决于输入实例中数据的状态。 文件的顺序存储结构表示 #define n l00 //假设的文件长度,即待排序的记录数目 typedef int KeyType; //假设的关键字类型 typedef struct{ //记录类型 KeyType key; //关键字项 InfoType otherinfo;//其它数据项,类型InfoType依赖于具体应用而定义 }RecType; typedef RecType SeqList[n+1];//SeqList为顺序表类型,表中第0个单元一般用作哨兵 注意: 若关键字类型没有比较算符,则可事先定义宏或函数来表示比较运算。
【例】关键字为字符串时,可定义宏"#define LT(a,b)(Stromp((a),(b))<0)"。那么算法中"a
答:可以参考一下《算法导论》,如果想了解目前研究现状,建议找一个最近具有权威性的综述详情>>
答:我建议你去--天下网吧联盟 这里面都是网吧业主和网管交流的论坛,你可以自己注册一个用户进去看看,你可以和他们交流也可以寻求他们的帮助,我想没有你解决不了的问题,...详情>>
答:格式化文本区域的段落标记,用于规定文本和层的属性和位置等。比如: 新浪网 用来规定 新浪网 这三个字居中显示。 文本中心(CENTER)、左(LEFT)或右(R...详情>>