|
排序算法分析 排序算法的基本操作 大多数排序算法都有两个基本的操作 () 比较两个关键字的大小; () 改变指向记录的指针或移动记录本身 注意 第()种基本操作的实现依赖于待排序记录的存储方式 待排文件的常用存储方式 () 以顺序表(或直接用向量)作为存储结构 排序过程对记录本身进行物理重排(即通过关键字之间的比较判定将记录移到合适的位置) () 以链表作为存储结构 排序过程无须移动记录仅需修改指针通常将这类排序称为链表(或链式)排序; () 用顺序的方式存储待排序的记录但同时建立一个辅助表(如包括关键字和指向记录位置的指针组成的索引表) 排序过程只需对辅助表的表目进行物理重排(即只移动辅助表的表目而不移动记录本身)适用于难于在链表上实现仍需 避免排序过程中移动记录的排序方法 排序算法性能评价 () 评价排序算法好坏的标准 评价排序算法好坏的标准主要有两条 ① 执行时间和所需的辅助空间 ② 算法本身的复杂程度 () 排序算法的空间复杂度 若排序算法所需的辅助空间并不依赖于问题的规模n即辅助空间是O()则称之为就地排序(InPlaceSou) 非就地排序一般要求的辅助空间为O(n) () 排序算法的时间开销 大多数排序算法的时间开销主要是关键字之间的比较和记录的移动有的排序算法其执行时间不仅依赖于问题的规模还取决 于输入实例中数据的状态 文件的顺序存储结构表示 #define n l //假设的文件长度即待排序的记录数目 typedef int KeyType; //假设的关键字类型 typedef struct{ //记录类型 KeyType key; //关键字项 InfoType otherinfo;//其它数据项类型InfoType依赖于具体应用而定义 }RecType; typedef RecType SeqList[n+];//SeqList为顺序表类型表中第个单元一般用作哨兵 注意 若关键字类型没有比较算符则可事先定义宏或函数来表示比较运算 【例】关键字为字符串时可定义宏#define LT(ab)(Stromp((a)(b))<)那么算法中a 用C++，则定义重载的算符"<"更为方便。 |
