《一种双向冒泡排序算法的C语言实现及其效率分析》由会员分享，可在线阅读，更多相关《一种双向冒泡排序算法的C语言实现及其效率分析（3页珍藏版）》请在金锄头文库上搜索。
1、 一，一一一 一箍 一 堡 一 照一 一 ， 一 ，一，一 ， 鼹 j AN COM PU下 三 敞 一种双向冒泡排序算法的 C语言实现 及其效率分析 龚 佳， 刘远军 ( 邵阳学院 信息工程系湖南 邵阳4 2 2 0 0 4 ) 【 摘 要】 ： 针对内部排序中的交换类排序算法， 分析了冒泡排序算法的不足， 探讨了对传统冒泡算 法的改进， 提 出了一种双向冒泡排序算法并用C语言予以实现， 最后对其效率进行了分析。 【 关键词】 ： 内部排序； 交换类排序； 冒泡算法； 双向冒泡 1引 言 随着大数据时代的到来， 当今计算机处理的数据 越来越大 ， 如何在海量数据 中查找有用的数据 ， 已经
2、是一个值得研究和探讨的话题 。为了提高查找的效率 或者是因为其他的要求 ，往往要先对数据进行排序 。 根据数据存储的位置不同， 可以分为 内部排序和外部 排序， 就算法而言 ， 我们更 多的关心 内部排序 ， 而外部 排序 ， 则主要关心其存储结构 的实现 。本文将讨论 内 部排序中常见的冒泡排序及其改进的双 向冒泡排序 ， 并将对两者之 间的效率进行定量的分析。 2交换类排序算法 内部排序算法根据其数据处理方式的不同， 一般 可 以分为插入类排序 ( 如直接插入排序、 折 半插入排 序 、 希尔排序等) 、 交换类排序 ( 如 冒泡排序、 快速排序 等) 、 选择类排序 ( 如简单选择排序
3、、 树形选择排序等) 三大类【 ” 。此外， 还有一些特殊形式的排序算法 ， 比如 归并排序 、 分配排序等等 。 交换类排序是其 中非常重要的一类排序法 。 它 的 思想是通过 多步交换一系列 的逆序元素对 ， 最终达到 消除全部逆序， 实现有序的目的。交换类算法有着临 时存储空间占用小， 算法简洁的优点， 最常见的两种 交换类算法是冒泡算法和快速排序算法 。 快速排序算 法是已知的时间效率最高的算法 ， 尤其是面对超大量 数据 的排序 时， 快速算法的时间效率明显 比其他算法 高出一个数量级。 但是， 快速排序算法也有其缺点， 它 是一种不稳定的算法， 对于一些关键值相等的数据记 录 ，
4、它可能会改变数据记录 的原始顺序 ， 这就限制 了 它的使用 ， 有一些场合 ， 例如医院挂号排 队、 学生成绩 基金 项 目： 湖南省教 育厅一般科研项 目资l h ( 1 2 C0 8 6 3 ) 排序等， 必须要求排序算法是稳定 的， 即对 于相等 的 若干条值， 原始顺序在前面， 排序以后也必须在前面。 冒泡算法是一种非常简单、 易于实现的算法， 在运行 效率上它不如快速排序算法 ， 但是它运算简单、 稳定 ， 适合于一些小规模数据的排序 ，特别是因为其稳定 性 ， 它可以适用于任何场合。 3冒泡算法 3 1普通 冒泡算法 冒泡算法的基本思路是分趟进行 比较 ， 消除逆序 圜。假设有
5、N个元素， 要按升序排序， 用 冒泡法具体算 法设计如下 ： ( 1 )先比较第 i 个元素和第 2 个元素，如果第 i 个元素的值大于第 2个元素， 则交换这两个元素的位 置 ， 这样 ， 前两 个元素 中， 较大的元素在后面 的位置， 然后 ，以此类推，两两比较第 i 个元素和第 i + 1 个元 素， 如果第 i 个元素的值大于第 i + 1 个元素的值 ， 则交 换第 i 个和第 i + 1 个元素的位置 。 也就是说， 每次把较 大的元素往后沉一个位置， 经过这一趟 比较， 最大 的 那个元素将沉入最底层 ， 即处在 N的位置。 ( 2 ) 对前 N 一 1个元素， 重复 ( 1 )
6、 的步骤。 ( 3 ) 以此类推， 重复 ( 1 ) 和 ( 2 ) 的步骤 。 原始的 冒泡排序算法有一个缺 点， 如果数据本来 就是有序 的，或者经过几 次交换后就马上变成有序 了， 算法不能 自动识别， 还是要经行 N 一 1 趟比较 ， 这就 浪费了大量的运行 时间，我们可以引入一个监视哨， 用来监视数据的交换情况， 如果某一趟排序中， 数据 序列中的数据元素 已经没有交换了， 我们就可 以认为 排序 已经完成 ， 不需要再进行剩下的比较 。现用 C语 2 0 1 3 年 第1 1 期 l 福建电脑 5 5 一 一一一 惫 亍 一 一 言将 引入监视哨的冒泡算法实现如下： ma i n
7、 0 i n t S E 3 0 0 0 ， t ,i , j ， n ， s c o r e = O ， e o u n t = O ， fl a g ； s c o r e表示交换次数； c o u n t 表示比较趟数。 p ri n ff ( ” P l e a s e i n p u t n ： ” ) ； s c a n ff ” d I ， n ) ； i n s e r t ( s ， n ) ； i n s e r t 函数用来生成 3 0 0 0以内的随机数 。 p r i n t ( s ， n ) ； p ri n t 函数用来输出数组元素。 fl a g = 1 ；
8、fl a g 监视哨。fl a g为 1时表 示有数 据交换，为 0 时表示无数据交换。在第一趟比较之前默认有数据交换。 f o r ( i = 1 ； i n & fl a g = = 1 ； i + + ) fl a g = O ； 监视哨， 这里设置为无数据交换 f 0 r ( j = 0 s j + l - I ) t = s E j 3 ； s j = s E j + l ； s j + 1 = t ； s c o r e + + ； fl a g = l ； ， s c o r e+l i f ( fl a g )c o u n t + + ； 如果有数据交换， 比较趟数+ 1 。
9、 p r i n t ( s ， n ) ； p r i n t f ( ” a s c o r e = d W , s c o r e ) ； p r i n ff ( ” k n c o u n t = d , c o u n t ) ； 以上程序可 以对 随机生成 的 n个整数进行排序 ， 其中f l a g 作为监视哨，用来识别是否有数据交换， s c o r e 用来记录总的数据交换次数， c o u n t 用来记录总 的比较趟数 。 3 2带监视哨的双 向冒泡算法 双 向冒泡算法是对普通 冒泡算法 的一种改进， 它 的思路是， 每一趟 比较 时， 既要从前往后扫描， 两两比 较
10、， 将大数往后 沉 ； 同时也要从后往前 扫描 ， 两两 比 较 ， 将小数往前冒。这样， 每一趟 比较， 既能将最大数 沉入到最底层位置，也能将最小数置入最上层位置， 因而大大提高了普通 冒泡算法 的效率 ， 我们给 出 C语 言实现如下： ma i n 0 i n t s 1 3 O 0 0 3 ， t ， i , j ， l e ft ， ri g h t ， fl a g ， k ， n ， s c o r e = O ， c o u n t = O ； p ri n ff ( ” L n P l e a s e i n p u t n ： ” ) ； s c a n f( ” d ”
11、 ， &n ) ； i n s e r t ( s ， n ) ； i n s e r t 函数用来生成 3 0 0 0以内的随机数。 p ri n t ( s ， n ) ； p ri n t 函数用来输出数组元素。 l e ft = O ； r i g h t = n 一 1 ； fl a g = 1 ； fl a g为监视 哨 w h i l e ( 1 e f t r i g h t & fl a g ) fl a g = O ； f 0 r ( i = 0 ； i s j + 1 ) 5 6 福建电脑 I 2 o 1 3 年 第1 1 期 t = s j ； s j = s j +
12、1 ； s j + 1 = t ； fl a g = 1 ； s c o r e + + ； ) i f ( s E k = 5 0 0 ) ， 普通 冒泡排 序的比较趟数接近n ，双向冒泡排序的比较趟数接近 n 2 ， 它们的效率都变得很低 。 所 以， 这两种排序算法都 只能适用于小规模的数据排序 。 4结束语 在数据的处理中， 数据的内部排序有着非常重要 的地位 ， 虽然对于大规模数据排序 ， 最 为有效的还 是 快速排序算法 ， 但是对于必须要求稳 ( 下转第 9 4页) 一一 |UJ遁I A 亍璺一 一 一 此， 它破坏原有模式的概率很大 ， 但与此同时， 他又能 寻找到一些前面基于
13、点交叉方法无法搜索到的模式 。 相 比之下 ， 单点或多点交叉保护好原有模式的概 率较大 ， 均匀交叉有具有较高的搜索能力， 因此 ， 当种 群规模较大时， 种群 中的多样性 已经不需要再去搜寻 什么新的模式， 此时 ， 可 以采用单点或多点交叉来保 证原有 的模式， 而 当种群规模较 小时， 则采用 均匀交 叉 的方式比较可行。 4 、 适应度函数设计 在生物进化 的过程 中有环境作为标准对 生物进 行优胜劣汰的选择，那么在遗传算法 的设计过程中， 谁来充当环境这一角色来对产生的新种群， 新个体进 行筛选呢?这就需要用到适应度函数 了。 适应度函数是将 问题 的潜在解 以适应值得方式 将其标
14、准化， 从而判断哪一种解才 是最合适的。因此， 它必须有能力来计算搜索空间中每个确定长度 的特 征字符 串的适应值 。通常情况下 ， 适应度函数是 问题 本身所具有的， 只要将 问题要求得的解 函数化 即可得 到相应 的适应度 函数 。 对于本例题而言， 由于我们 的目标是找到 n个数 使他, f f 的和最小，那么在这里将适应度 函数就设为 n 个数的和 ， 每次对 比新得到的矩 阵中这 n个数 的和与 杂交前和的大小 ， 若 比杂交前 大 ， 则说 明不适 应“ 环 境” ， 将其淘汰。若小， 则说明适 l立 环境” 。 5 、 算法终止准则的设计 由于遗传算法的很多控制规则都是随机 的，
15、 没有 利用 目标函数的梯度等信息， 所以在遗传算法的过程 中，无法控制和掌握某一解在解空间的具体位置， 也 就无法利用传统的方法对算法进行终止 。因此 ， 通 常 采用的终止算法的方法是预先规定好最大演化代数， 连续多带后的解的适应值没有明显变化 ，则终止 ， 或 者说达到明确解 目标时终止算法。 在本题 中， 我们就给定一个变量 ， 由它来控制 演 化 的代数，这个变量用 # d e fi n e来定义，以便随时修 改， 来调整演化代数。 6 、 小结 演化算法提供 了一种与传统算法截 然不同的求 解问题的方法， 它的主要优点在于概念简单， 易于理 解和操作 。它的基本思想是 ： 基于达尔
16、文进化论 中适 者生存、 优胜劣汰的基本原理 ， 按生物学 的方法将 问 题的求解表示成“ 种群 ” ， 一般 以二进制码 串的形式表 示 ， 从而构造 出多个可行解 的空间， 然后选择一种最 合适的方法进行杂交，将的产生的子 串放入 “ 环境 ” 中， 根据适者生存 的原则， 对这些子 串进行遗传学基 本操作 ， 不断优化成新 的种群 ， 这样一代代地不 断进 化 ， 最后得出一个最 能适应环境的二进制码 串， 将其 解码， 即可得到问题的最优解。 参考文献 ： 1 朱福喜 人工智能基础教程 M 北京： 清华大学出版社， 2 01 1 2 王宏生人工智能及其应用 M 北京：国防工业出版社 ，
17、 2 0 06 3 王文杰， 叶世伟 人工智能原理与应用 M 北京： 人民邮电 出版 2 0 0 4 4 蔡 自兴， 徐光口 人工智能及其应用第三版 M 北京： 清华 大学出版社， 2 0 0 4 5 金聪， 郭京蕾 人工智能原理与应用 M 北京： 清华大学出 版 社 2 0 0 9 6 ( 澳) Mi c h a e l Ne g n e v i t s k y著，陈薇等译 人工智能 M 北 京： 机械工业 出版社 ， 2 0 1 2 7 葛继科， 邱玉辉 ， 吴春明， 蒲国林 遗传算法研究综述 J 计 算机应用研究， 2 0 0 8 ， 2 5 ( 1 0 ) ： 2 9 1 1 2 9
18、1 6 8 王银年 遗传算法的研究与应用 D 江南大学， 2 0 0 9 9 朱灿 实数编码遗传算法机理分析及算法改进研究 D 中南 大学， 2 0 0 9 1 0 吉银林 遗传算法研究综述 J 计算机应用与软件， 2 0 0 4 ， 2 1 ( 2 ) ： 6 9 - 7 3 ( 上接第 5 6页) 定性的特殊场合下中小规模数据排序而言， 冒泡排序 还是有着 良好的应用。本文探讨 了对 冒泡算法引入监 视哨， 改进为双向冒泡排序， 力争达到有效减少比较 趟数， 提高运行效率 的 目的， 实践数据证明， 这种改进 有是有效的。 9 4 福建电脑 l 2 o 1 3 年 第1 1 期 参考文献 ： 1 陈卫卫， 王庆瑞 数据结构与算法 M 北京： 高等教育出版 社 2 0 1 0 2 耿国华 数据结构用 C语言描述 M 北京： 高等教育 出版 社 ， 2 0 1 1
