往后→ ←往前 h〔1) 尾（队列1）头 Point ACN) L尾（队列Hm)头 L头（队列Hm十1）尾 头（队列m)尾： 均为第一种元紫 均为第Hm种元素 均为第Hm千1种元素 均为第如 分 种元恭 PHm-上 PHm 案 PHe+1 PHm+2 (图二)正在分类时 三、算法分析 ①分类效率 分类效率既是元素分类时平均比较次数。山算法不难得出，在建立关键字值数组VAL UE时，所需比较次数为N·LOG2M,这是因为对M个已分类数据采用折半查找法查找指 定元素或判别其不在值数组中所需比较次数为LOG2M。在执行算法第(2)步判断一个 元素所属种类时，需LOG2M次比较，N个元素共需(N·LOG2M)次比较。综上所述， 本算法，总的比较次数为O(NLOG2M),排序效率为O(NLOG2M)。 ②每一项移动的平均次数 在建立关键字值数组VALUE时，在最坏情况下，关键字所需移动的总次数为M(M- 名一1 1)/2（-)。不尖一般性，假设每一元素在数组A中任何位置出现是等概率的，即 P;=1/N。那么，在执行算法第(2)步时，若每一个元素属于任何一类元素是等概率 的，即q1=1/M,则分类一个元素所需移动元素的次数为：M/4。这由下式推得， 2 j= M (这里P,=,1=1/M) 在最坏情况下，即元素堆集在两头，其关键字或者较大或者较小时，不难推导出每分类一 个元素所需移动元素的次数为M/2。 综上所述，分类M种共N个元素所需移动元素的总次数为O(M·N),所移动关键 字的总次数为O(M2)。 ③附加空间 本算法所需附加空间取决于分类元素的种类数M。具体米说，需M个指针单元，M个 元素关键字单元。因此，当每一个元素所占空间远大于其关键字和指针所占的空间时，本 算法就更加适用。 从算法可以推得，当分类元素按关键字值服从正态分布时，或者元素堆集在中间时， 调用本算法分类这些元素所需移动元素次数会减少。另外，若我们初始已知元素的种类数 92往后叶 朴在前 层 队列 二 头 －一 一 均为第 种－元素 头 队列 二 尾 〔 〕 头 队列二 尾 ， 」勃履而 一一 种元索 均 为第 种元素 元素分类待 一爪 ” 功 一 二 ” … … …” 口 图二 正 在分 类时 三 、 算法分析 ①分类效率 分类效率既是元素分类时平均比较次 数 。 由算法 不难得 出 ，在建立关键字值数组 时 ， 所需比较次数为 · ， 这是 因为对 个己分类数据采用折半查找法 查找指 定元素或判别其不在值数组 中所需比较次数为 。 在执行算法第 步判 断一 个 元素所 属种类时 ， 需 次 比较 ， 个元素共需 · 次 比较 。 综 上所述 ， 本算法 总的比较次数为 ， 排序效率为 。 ②每 一项移动的平均次数 在建立 关键字值数组 时 ， 在最坏情况下 ， 关键字所需移动的总次数为 。 不失一般性 ， 假设每一元素在数组 中任何位置 出现 是 等概率的 ， 刹玖 即 。 那 么 ， 在执行 算法第 步 时 ，若每一 个元素属于任何一 类元素是 等 概 率 的 ， 即 二 ， 则分类一个元素所需移动元 素的次 数为 。 这 由下式推得 ， 竺 三 〔 ，叠 乙 一 瞥 ， 〕 ‘ 。 。 竺 一 一 ， 、 、 ‘ ，，， 。 、 〕玉 且兰 下节 ， 、 了竺 、 、‘ ， 在最坏情况下 ， 即元素堆集在两 头 ， 其关键 字或者 较大或 者较小时 ， 不难推导 出每分类一 个元素所需移动元素的 次 数为 邝 。 综上所述 ， 分类 种共 个元素所需 移动元 素的总次 数为 · ， 所移 动 关 键 字的总次数为 “ 。 ③附加空间 本算法 所需附加空 间取 决于分 类元素的种类数 。 具体来说 ， 需 个指针单元 ， 个 元素关键 字单元 。 因此 ， 当每一个元 素所 占空 间远 大于其关键字和指针所 占的空 间时 ， 本 算法就更加适 用 。 从算法可 以推得 ， 当分类元素按关键字值服从正 态分布时 ， 或者元素堆集在中间时 ， 调用本算法分类这些 元素所需移动元 素次数会减少 。 另外 ， 若我们初始已知元素的种 类数