什么是二路归并排序 排序 - 分配排序 - 箱排序 （二）

排序 - 分配排序 - 箱排序 （二）  

　　 )在基于比较的排序方法中 每次比较两个关键字的大小之后 仅仅出现两种可能的转移 因此可以用一棵二叉树来描述比较判定过

　　程

　　当文件的n个关键字随机分布时 任何借助于 比较 的排序算法 至少需要O(nlgn)的时间

　　箱排序和基数排序只需一步就会引起m种可能的转移 即把一个记录装入m个箱子之一 因此在一般情况下 箱排序和基数排序可

　　能在O(n)时间内完成对n个记录的排序 但是 箱排序和基数排序只适用于像字符串和整数这类有明显结构特征的关键字 而当关键

　　字的取值范围属于某个无穷集合(例如实数型关键字)时 无法使用箱排序和基数排序 这时只有借助于 比较 的方法来排序

　　若n很大 记录的关键字位数较少且可以分解时 采用基数排序较好 虽然桶排序对关键字的结构无要求 但它也只有在关键字是

　　随机分布时才能使平均时间达到线性阶 否则为平方阶 同时要注意 箱 桶 基数这三种分配排序均假定了关键字若为数字时 则

　　其值均是非负的 否则将其映射到箱(桶)号时 又要增加相应的时间

　　( )有的语言(如Fortran Cobol或Basic等)没有提供指针及递归 导致实现归并 快速(它们用递归实现较简单)和基数(使用了指

　　针)等排序算法变得复杂 此时可考虑用其它排序

　　( )本章给出的排序算法 输人数据均是存储在一个向量中 当记录的规模较大时 为避免耗费大量的时间去移动记录 可以用链表

　　作为存储结构 譬如插入排序 归并排序 基数排序都易于在链表上实现 使之减少记录的移动次数 但有的排序方法 如快速排序

　　和堆排序 在链表上却难于实现 在这种情况下 可以提取关键字建立索引表 然后对索引表进行排序 然而更为简单的方法是 引

　　人一个整型向量t作为辅助表 排序前令t[i]=i( ≤i )，若排序算法中要求交换r[i]和r[j]，则只需交换t[i]和t[j]即可;排序

　　结束后，向量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)。wInGWit.CoM