|
)在基于比较的排序方法中每次比较两个关键字的大小之后仅仅出现两种可能的转移因此可以用一棵二叉树来描述比较判定过 程 当文件的n个关键字随机分布时任何借助于比较的排序算法至少需要O(nlgn)的时间 箱排序和基数排序只需一步就会引起m种可能的转移即把一个记录装入m个箱子之一因此在一般情况下箱排序和基数排序可 能在O(n)时间内完成对n个记录的排序但是箱排序和基数排序只适用于像字符串和整数这类有明显结构特征的关键字而当关键 字的取值范围属于某个无穷集合(例如实数型关键字)时无法使用箱排序和基数排序这时只有借助于比较的方法来排序 若n很大记录的关键字位数较少且可以分解时采用基数排序较好虽然桶排序对关键字的结构无要求但它也只有在关键字是 随机分布时才能使平均时间达到线性阶否则为平方阶同时要注意箱桶基数这三种分配排序均假定了关键字若为数字时则 其值均是非负的否则将其映射到箱(桶)号时又要增加相应的时间 ()有的语言(如FortranCobol或Basic等)没有提供指针及递归导致实现归并快速(它们用递归实现较简单)和基数(使用了指 针)等排序算法变得复杂此时可考虑用其它排序 ()本章给出的排序算法输人数据均是存储在一个向量中当记录的规模较大时为避免耗费大量的时间去移动记录可以用链表 作为存储结构譬如插入排序归并排序基数排序都易于在链表上实现使之减少记录的移动次数但有的排序方法如快速排序 和堆排序在链表上却难于实现在这种情况下可以提取关键字建立索引表然后对索引表进行排序然而更为简单的方法是引 人一个整型向量t作为辅助表排序前令t[i]=i(≤i 结束后，向量t就指示了记录之间的顺序关系： R[t[0]].key≤R[t[1]].key≤…≤R[t[n-1]].key 若要求最终结果是： R[0].key≤R[1].key≤…≤R[n-1].key 则可以在排序结束后，再按辅助表所规定的次序重排各记录，完成这种重排的时间是O(n)。tw.WInGwiT.COM |
