关于数组排序方法的讨论.pdf

1 9 9 9 年第2 期 童 委 甜技 6 1 一 2 关于数组排序方法 的讨论 ／ 中国矿 业大学北京校 区 李耀辉杜剐 朱 曦光 摘要分析了数组排序常用几种方法的比较次数、 交换次数以及数 对间的关系， 并且指 出了各种算法的优缺点和适用的场合。 关键词 交换浩选择法括八法Q u ic k s o r t 排序法 ／ q 在计算机应用 中， 尤其在设计数据库时， 常 常碰到排序的问 题。 排序曲甄狺看两种基 本类型 数组排序和文件排序 ， 文件排序又分 为随机文 件排序 和顺 序 文件 排 序。数组 排序 的基本方法 有 三种 交换法 、 选择 法 、 插 入法 。 由于算法不同， 排序速度也各不相 同。 1 交换法 1 ． 1 冒泡排序法 冒泡法是一种常用的方法， 其优点是简 S h e l l 排序 法 1P } 8 组中的元素个数与运行 锄 单。它从数组的一端开始， 依次对相邻的两元 素进行比较， 当发现它们不合顺序时 ， 就进行 一 次交换 。对于一个元 素为 1 “1 的数 组 ， 比较 的 次数共需 n 1“1 1 1 2次。平均情况下交换次 数为 3 n n一1 ／ 4 ； 因为 每交 换 一对 不 合顺 序 的元素， 需进行三次操作 ， 所 以最坏情况下， 交 换次数是 比较次数 的三倍， 即 3 n n一1 1 2 。 因此 ， 冒泡法 是 效率最 差 的排 序方 法 ， 一般 只 适合于数组较小的情况。 2． 3控制 过程 图2中 1 c 、 2 c 、 3 C 、 4 C为红外线传感器， 每组有发射和接受两部分分别安装在巷道的 不同位置的两壁上， 用以探 测过往的车辆 5 c 和 6 C是接近传感器 ， 分别安装在 A 、 B两 门框 上 ， 用以探测 门的开闭状态 。 当车辆由巷道的 A端 向 B端行驶时， 首 先传感器 1 c动作 ， A门打开。 当车辆继续行进通 过 A门后 ， 到达传感 器 3 c时 A门闭合。 A门闭合， 使传感器 5 c动作 ， B门打开。 当车辆行进通过风 门 B到达传感器 4 C 时 ， B门闭合 ， 此时全部控制过程完毕。 当车辆由巷道的 B端向 A端行驶 时， 动 作原理同上。 3 技 术关 键 风门两侧空气有一定 的压差， 由于风门的 面积很大 ， 一般风门的开启压力为 3 0 5 o k g 。 当风门有较小 的开启时 ， 这个压力就锐减 到 5 以下， 为 了减少开启压力 ， 在风门上设 置 一 个窗E l 。由于窗的面积较小 ， 其开启压力只 有 1 0 k g 左右 ． 当窗口打开后， 门的两侧压差大 大减小 。先开窗后开门的技术措施， 可以减小 机构的强度及气缸的操作力 。 4结语 井下风门实现自动化， 可解决风门人工开 关 、 运输不便的问题 ， 防止风 门撞车事故发生。 维普资讯 互 茬科技 1 9 9 9 年第2 期 1 ． 2 拉锯排 序法 拉锯 法 是 对 冒泡 法 的一 种 改 进。“ 拉锯 式” 算法不再是总按同一方向读数组元素， 而 是这一遍从下到上把最小的送到最上的位置， 下一 遍从 上到下 把最 大的元 素送 到最 下的位 置。其算法是来 回搜索， 好像拉锯一样。拉锯 法的比较次数仍是 n n 一1 ／ 2 ， 交换次数只是 减少了一个较小的常数 ， 所以执行时问仍然是 与元素数 目n的平方成正比例增加。 2 选 择排序法 选择排序法从数组中选择数值最小的一 个元素， 把它和位于第一个位置的元素交换位 置， 然后从剩下的元素 中选择最小的一个元 素， 并把它和这些元素中的第一个相交换， 不 断重复这些步骤， 直至最后两个元素。其总的 比较次数是 n n 一1 ／ 2次， 故仍不适用于数目 较大的数组。 尽管选择排序法比较次数没有改进 ， 但是 交换次数有所减少 ， 最坏情况下交换次数接近 于比较次数 ， 为 [ n 2 ／ 43 n一1 】 。平均情况 下交换次数为[ n xI l 1 n u ] ， 其中 u是尤拉 常数， 约为 0 ． 5 7 7 2 1 6 。 3 插入排序 法 插入排序法首先对数组的头两个元素进 行排序， 然后从数组中取 出第三个元素 ， 把它 与已经排好序的前两个元素比较 ， 插在它所应 该在的位置。重复这个过程， 直至最后一个元 素。插入排序法的比较次数和交换次数与被 排序数组的初始顺序情况有关， 在最好、 最坏、 平 均三种情况下， 总的比较次数分别是 n 一 1 、 n 2 n一2 ／ 4 、 n 2 n ／ 2 1 ， 总 的交换 次 数分别是 2 n一1 。 n 2 9 n 一1 O ／ 4 、 3 n 一 4 ／ 2 。由此看出， 在最坏情况下， 插入排序 法的交换次数与冒泡法、 选择法一样糟糕 ， 其 执行时间基本和 成正比。 为了提高排序的速度， D ． L ． S h e l l 发明了 S h e ll 算法 ， 其基本思 想是插入法。S h e ll 法首 先把整个数组分成 n 部分 ， 分别进行处理。处 理完毕后 ， 再合起来 ， 又再分成少数几个更大 的部分， 再分别进行处理。直至最后只分为一 个部分。因为各部分的元素较少 ， 又因为每一 遍都会增加数组的顺序 ， 为下一遍采用插入法 提供了较好的基础 ， 故总的排序速度很快。 例如对数组 6 ， 4 ， 1 ， 3 ， 2 ， 5 排序。第一遍 每 隔两个元素 元素号增量 为 3 组成 一个组 ， 分为三部分 6 、 3 ， 4 ⋯ 2 1 5 ， 分别对这三组数排 序得到 3 ⋯ 2 1 6 ⋯ 4 5 第二遍每隔一个元素 元素号增量为 2 组成一个组， 分为两部分 3 、 1 、 4和 2 , 6 、 5 分别排序。第三遍不再划分 元 素号增量为 1 ， 统一排序， 如图 1 。 妊 厶 ／ 一 ／ ● 三 遗l ～ 结 果 I 困 1 S h e l l 排序过 程 困 元素号增量的具体顺序不要求一定是 3 ， 2 ， 1 ， 可 以改 变 ， 但 要遵 循 的是 最 后一 次是 1 。 在 比较时 ， 应 找合适 的增 量 ， 同时应尽 量 避免 使用 2的幂次方作为增量序列， 因为这会使排 序算法的效率降低。 在 S h e ll 排序法中， 如果被排序数组有 n 个元素． 排序的执行时间与 n ’ 成正 比。所以 该算法有极大的改进 ， 不失为一种较好的的算 法 。 4 Q u i c k s o t t 排序法 o I l ic k s o r t 排序法是 由 C ． A． R ． H o e m e 发明 和命 名 的， 现 在 被誉 为 是 最 好 的排序 法 ， Q I lj c bo r t 排序法 从根本上说是属 于交换 法。 其工作过程是首先选择一个分界值， 把数组分 为两部分 ， 大于或等于分界值的元素集中到数 组的某一部分 I ／ J 、 于分界值的元 下转 6 3页 维普资讯 1 9 9 9 年 第2 期 互媳晨 科救 G2 5 8 6 一 ‘ 论 高校 建立 电子 阅览 室的 必 要 性 和 可 行 性 河 南省洛 阳大学 图书馆杨 一丁 摘要本文从理论 上对高校 图书馆建立 电子 阅览 室的必要性和可 行性进 行 了阐述 ， 提 出了 参考意见。 关键词高校图书馆建 立电子 阅览 室 ／ ，一 9 0年代 以来 ， 现代科 学技术 It 新月异。 信息高速公路的迅速发展， 电子文献的迅猛增 长， 给图书馆信息情报工作提出了新的课题。 图书馆做为人类文化的宝库 、 最大量的信息情 报集藏基地， 也受到飞速发展的信息技术的推 动 ， 正在 发生着深 刻而 快速 的变化。 图书馆 自动化是图书馆迈 向信息现代化 的初级阶段， 主要是对采编、 流通 、 剔旧等工作 利用计算机改变繁杂的工作程序 ， 摆脱繁重的 手工操作， 提高工作效率和服务质量。这项工 作高校图书馆已基本普及。 虚拟图书馆是 图书馆发展 的高级 阶段 网络技术和超文本技术的迅速发展， 使图书馆 界在 数字 图书馆 的基础 上提 出 了虚拟 图书馆 的概念。它的硬件基础是连接全球 的国际网 络， 读者并不需要知道要问哪一个图书馆而只 需在网络上发出阅读请求， 网络就可给你调出 该书来， 该 书可以来 自世界 上任何一个图书 馆。读者是在与世界上所有图书馆打交道， 所 以虚 拟图书 馆又可 叫全球 图书馆 。 数字图书馆作为 图书馆发展的第二个阶 段是把经过数字化处理 的信息存储在软盘、 光 盘中， 借阅者通过计算机联机阅读 ， 主要信息 源是电子出版物和传统出版物的电子化。电 子阅览室是数字图书馆发展的前提 ， 它的建立 ， 5 f j ． 讲 3 奠定 了向数字 图书馆发展 的基础 。 高校图书馆担负着为教学科研最快提供 最新最准的信息情报的任务。要想生存与发 展 ， 必须接受新意识、 新观点 ， 用战略的眼光采 取各种对策 ， 迎接信息时代的挑战。建立电子 阅览室是一条捷径。电子阅览室这一新产物 ， 在沿海发达地区高校图书馆已很普及 ， 但欠发 达地区基本上还是空白。建立电子阅览室是 图书馆工作 的当务之 急。 电子阅览室是利用计算机或者有类似功 能的设备阅读网络上 的信息， 如中国教育科研 网 c E 唧 、 因特网 I n t e lT le t 和电子文献 软 盘、 光盘 等。读者可以从屏幕上和打印机等 其它设备上快速 、 准确获取 自己所需要的最新 的信息情报 。这是一般阏览室所不能 比的。 最能体现 电子阅览室特点的， 还应是它利 用的信息源一网络和电子文献。网络有国内 网络和国际网络， 根据学科不同各种网络都有 自己的特性。不论何种网络都是为了资源共 享。联接它们能在最短时间内获取国内外最 新的政治、 经济、 技术、 文化等信息， 而且价格 便宜。电子文献作为电子阅览室的信息源之 一 ，有它不可替代的优势 第一 ， 容量大， 一张 5 寸低密软盘可存储约 l 8万汉字 ， 一张高密 软盘可存储约 6 o万汉字， 一张普通光盘可存 维普资讯