一种改进的冒泡排序算法

Ａ　Ｎｅｗ　Ｉｍｐｒｏｖｅｄ　Ｓｏｒｔｉｎ９　Ａｌ９ｏｒｉｔｈｍ　王俊亭　曹建芳　ｗａｎｇ　Ｊｕｎｔｉｎｇ　Ｃａｏ　Ｊｉａｎｆａｎｇ　（１．忻州市工业学校教务处，山西忻州０３４０００；２．忻州师范学院计算机系，山西忻州０３４０００）　（１．Ｘｉｎｚｈｏｕ　Ｉｎｄｕｓｔｒｙ　Ｓｃｈｏｏｌ，Ｓｈａｎｘｉ　Ｘｉｎｚｈｏｕ　０３４０００；２．Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｃｏｍｐｕｔｅｒ，Ｘｉｎｚｈｏｕ　Ｔｅａｃｈｅｒｓ’Ｃｏｌｌｅｇｅ，Ｓｈａｎｘｉ　Ｘｉｎｚｈｏｕ　０３４０００）　摘要：提出了一种冒泡排序的改进算法，并对其性能与传统的冒泡排序算法的性能进行了实验比较。　关键词：排序；算法；算法复杂度　中图分类号：ＴＰ３０　１．６　文献标识码：Ａ　文章编号：ｌ　６７　ｌ一４７９２一（２０Ｏ８）７—００６７一Ｏ２　Ａｂｓｔｒａｃｔ：Ｔｈｉｓ　ｐａｐｅｒ　ｐｒｅｓｅｎｔｓ　ａ　ｎｅｗ　ｉｍｐｒｏｖｅｄ　ｓｏｒｔｉｎｇ　ａｌｇｏｒｉｔｈｍ　ａｎｄ　ｃｏｍｐａｒｅｓ　ｔｈｅ　ｐｅｒｆｏｒｍａｎｃｅ　Ｏｆ　ｔｈｅ　ａｌｇｏｒｉｔｈｎ　ｗｉｔｈ　ｔｈａｔ　ｃｏｎｖｅｎｔｉｏｎａｌ　ｂｕｂｂｌｅ　ｓｏｒｔｉｎｇ　ａｌｇｏｒｉｔｈｍ．　ＫｅｖｗｏｒｄＳ：Ｓｏｒｔｉｎｇ：Ａｌｇｏｒｉｔｈｍ；Ａｌｇｏｒｉｔｈｍ　Ｃｏｍｐｕｔａｔｉｏｎ　Ｃｏｍｐｌｅｘｉｔｙ　０　ｌ引言　顺序不对，则进行交换，并将标识变量ｆｌａｇ置ｌ，继续比　目前，最常见的排序算法有：冒泡排序法、选择排序　较；②若在某次循环结束后，ｆｌａｇ为０，则证明该数组已经　法、快速排序法。冒泡排序法是一种简单的排序算法，由于　性能很差，只有在待排数据量很小的时候才会选用它。选择　排序法的性能有很大的提高，但当待排数据量很大的时候，　排好序，不必再比较，循环结束。　２　ｌ排序算法　排序算法如下：　ｖｏｉｄ　ｂｕｂｂｌｅ（ｉｎｔ　ｉｔｅｍ［］；ｉｎｔ　ｎ）　｛　ｉｎｔ　ｉ，Ｊ，ｔｅｍｐ，ｆｌａｇ；　它也不能胜任。据悉，快速排序法在所有的排序算法之中，　效率最高，在对大数据量进行排序时常采用它。本文推出一　种效率更高的改进的冒泡排序算法。　１　ｌ一种改进的冒泡排序算法的思想　ｉｎｔ　ｂ［ＮＵＭ］；　／／存放每次排序的内循环次数　ｉｎｔ　ｐ；　ｆｌａｇ＝Ｏ；ｐ＝Ｏ；　传统的冒泡排序算法需要元素之间一次次相互比较，这　是影响排序速度的一个主要原因。随着待排元素个数的增　加，比较次数几乎呈几何级数增长。而这种改进后的冒泡排　序算法在大多数情况下，会减少待排数据之间的重复比较，　只要增加一个标识变量，如果在某次比较过程中，标识变量　未发生变化，则可证明数据已经有序，不必再进行比较，这　／／存放外循环次数　ｆｏｒ０＝１；ｉ＜ＮＵＭ；ｉ”）　ｂ［ｉ］＝０；　ｆｏｒ（ｉ＝ｌ；ｉ＜ＮＵＭ；ｉ＋十）　｛　ｆｌａｇ＝Ｏ；　样就大大提高了效率。下面是改进的冒泡排序的实验过程。　设待排序数组为一维数组Ａ，其元素个数为ＮＵＭ。　创建一个标识变量ｆｌａｇ，初始化ｆｌａｇ＝Ｏ。　排序开始：①将数组Ａ中的相邻元素进行大小比较，若　ｆｏｒ（Ｊ＝１；ｉ＜ＮｕＭ＿ｉ；Ｊ＋十）　｛　ｉｆ（ｉｔｅｍ［Ｊ］＞ｉｔｅｍ［ｄ＋１］）　维普资讯 http://www.cqvip.com

｛ｔｅｍＤ＝ｉｔｅｍ［Ｊ】；　ｉｔｅｍ［ｊ］＝ｉｔｅｍ［ｊ＋１］；　ｉｔｅｍ［ｊ＋１］＝ｔｅｍｐ；　ｆｌａｇ＝ｌ；）／／交换ｉｔｅｍ［Ｊ】与ｉｔｅｍ［ｊ＋ｌ】，并将ｆｌａｇ置１　ｂ［ｉ】：Ｌｊ；　根据实验数据可以看出：　当待排序元素基本有序时，本排序算法的时间复杂度会　大大降低，而传统的冒泡排序算法所需时间复杂度会随着待　排序元素个数的增加而大大增加。　５　Ｉ结论　－种　—＿　改　进　的　冒　泡　）　本排序算法在待排序元素大多有序的情况下，会大大节　排　ｐ＝ｉ；　ｉｆ（ｆｌａｇ－－０）　ｂｒｅａｋ；　省时间，降低算法的时间复杂度，有时其时间复杂度可达０　（ｎ），具有一定的实用性。　６　Ｉ本算法的优缺点　算　序　法　）　．　本算法只有在待排序数据元素基本有序的情况下，不愧　）　３＿与传统的冒泡排序法的实验比较　设数组Ａ有９个元素，按从小到大的顺序排序。　（１）如果待－Ｎ　的数组元素原来已经排序或只有相邻的　一为一种好算法，但如果待排数据元素杂乱无章，那本算法和　传统的冒泡排序法效果一样。在大多数场合下，本算法优点　大于缺点，是实用的。　对数未排好序（如：２，５，９，６，１７，１９，２３，５６，７ｓ），　参考文献　Ｋｅ。ｇｈ、Ｐ．Ａｉｔｋｅ　、Ｂ．Ｌ．Ｊ。　ｅｓ著．冯博琴等译．ｃ　语言程序设计轻松入门［ＭＪ北京：机械工业出版社，１９９６．　．．则本算法只执行８次循环即可结束，而传统的冒泡排序法需　执行９　８＝７２次循环；　【１】Ｊ（２）又如：ｘ，Ｉ－＝ｂ￣Ｎ（　２，　ｏ，２３，１９，４６，３７，７６，　９ｏ，９２），本算法只执行３ｏ次循环即可结束，而传统的冒泡　社，【２】谭浩强．ｃ程序ｔ２ｔｆ￣Ａ［．］．北京：清华大学出版　２ＯＯ７．　排序法需执行９　８＝７２次循环；　（３）再如：对于数据（　ＯＯ，９３，８５，８０，７８，７４，６ｏ，　５９，３４），本算法与传统的冒泡排序算法一样，需要执行７２　‘　［３］］ｕｚＮＬ￣．数据结构［Ｍ】．北京：清华大学出版社，２ＯＯ５．　ｃ程序设计试题汇编［Ａｆｊ．北京：清华大学　［４１谭浩强．出版社，１９９８．　次循环；　（４）经过反复实验比较，本算法在最坏的情况下，即所　有待　｝ｊ｝序元素顺序都不正确时，其时间复杂度与传统的冒泡　【５】徐德民．现代ｃ语言程序设计教程［Ｍ】．天津：南开大　学出版社，１９９４．　排序法一样，其余情况本算法的时间复杂度均小于传统冒泡　排序法的时间复杂度。而且可以看出：在数据量很大的情　况下，本算法在一定情况下可大大降低时间复杂度，这是很　实用的。４　ｉ实验结果的进一步分析　作者简介　王俊亭（１９７９　），男，大学本科　山西忻州市工业学　校教务处；　曹建芳（１９７６一），女，大学本科，硕士，山西忻州师　范学院计算机系。　１　４Ｑ