2022年程序设计中的排序及优化 .pdf

《2022年程序设计中的排序及优化 .pdf》由会员分享，可在线阅读，更多相关《2022年程序设计中的排序及优化 .pdf（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、收稿日期: 2006 - 09 - 04作者简介:杜恒(1976 - ) ,男,河南郑州人,河南工业职业技术学院教师。程序设计中的排序及优化杜恒,李怀刚,陈平(河南工业职业技术学院,河南南阳 473009)摘 要:排序是程序设计中很重要的一种操作,很多软件中都有排序的功能。而排序又是影响程序运行效率的重要因素,排序模块设计的好坏,直接影响到整个程序的性能。本文对常用的三种排序方法的实现以及如何优化进行深入的探讨。关键词:程序设计;排序;运行效率中图分类号:TP311111文献标识码: B文章编号: 1009 - 9522 (2007)02 - 0021 - 030 排序方法简介所谓排序就是将杂

2、乱无章的数据元素通过一定的方法按某种关键字进行从大到小或者从小到大进行排列的过程。排序是程序设计中一种常用而又非常重要的操作,在多数软件中都有体现,也是程序员在进行程序设计时常常要考虑的算法,但是多数程序员在实现排序的时候,往往只进行排序,而忽略了优化,致使设计出的程序运行速度非常慢,效率非常低。尽管说影响程序运行效率是多方面的,但是优化排序是提高程序运行效率的主要手段之一,所以必须要重视。排序的方法非常多,分为几个大类,如交换类、选择类 、插入类以及链式基数排序等。相应的又有几十种,如冒泡排序 、快速排序 、选择排序 、堆排序 、插入排序 、希尔排序等,在此我们主要讨论常用的三种排序,即冒泡

3、,选择及简单插入排序,并对这些排序算法进行优化。1 冒泡排序及优化111 冒泡排序的基本原理冒泡排序,又叫做起泡排序,其排序的规则是相邻的两个数进行两两比较,符合交换条件的进行互换,直到该轮的结束 。由于在排序过程中,某些数往前面排,而某些数排序时往后面去,而且一次移动个位置,往前面排的数好象水中的气泡在慢慢上升一样,所以我们把此种方法称为冒泡排序(本文所有排序均按从大到小排序)。112 冒泡排序的C语言实现算法由冒泡排序的基本原理及排序过程,我们用C语言编写冒泡排序的实现算法。void bubblesort (int a,int n)inti ,j ,t ;for (i = 0;i n -

4、1 ;i + +)for (j = 0 ;j n - 1 - i ;j + + )if (aj aj + 1 )/3 如果前面的数比后面的小,进行交换,将大数调在前面3/t = aj ;aj = aj + 1 ;aj + 1 = t ;此算法,是最基本的算法,按照排序的过程进行编写的 。从算法上来看,相邻两个数进行比较,如果前面的数比后面的数要小,就要进行比较和交换;否则的话,仅进行一次比较而不进行交换。而我们知道不管是进行比较的关系运算还是赋值运算,都要占用系统的执行时间,影响程序的执行效率 。如果在某一轮排序后,或者原序列已经有序,程序中所有的比较运算已不必进行了,而上述算法显然没有考虑这

5、一点 。我们现在对上面算法进行优化,设置一个标志,放在交换的语句序列中,如果执行到交换的代码,该标志即被修改,这样我们就可以判断此时正在进行排序;如果该部分代码不被执行,那么标志就不被修改,说明已经排序成功,下一轮就没有必要再进行排序了。我们利用这个标志来控制我们的算法的进行,这就是优化的算法。113冒泡排序的优化优化的算法如下:voidoptbubblesort(int a ,int n)12200712九 江 职 业 技 术 学 院 学 报(杜恒 : 程序设计中的排序及优化)名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名

6、师精心整理 - - - - - - - 第 1 页，共 3 页 - - - - - - - - - intI ,j ,t ,swap = 0 ;/3swap是用来判断是否排序好序的标志 3/for (i = 0 ;i n - 1 & & ! swap;i + + ) 3/当swap = 1时,取反为0 ,则退出循环3/swap = 1;for (j = 0;j n - 1 - i ;j + + )if (aj aj + 1 )t = aj ;aj = aj + 1 ;aJ + 1 = t ;swap = O ;/3swap为0 ,表示排序正在进行3/经过优化以后,我们可以看出,如果某一轮(比如

7、说在第i轮) ,执行完以后已经排好序了,那么下一轮(即i + 1轮)再进行一轮的判断,但是所有交换代码已不用被执行了,从而swap也不被执行,这样swap的值为1 ,那么在下一轮对swap的值进行取反为0 ,就可以退出循环了,从而有效的减少了无效的执行次数。这种优化的结果,如果对于待排元素比较少的序列,可能对算法执行效率的影响不是太大,如果待排元素个数有时是几百万甚至上亿的时候,效率的提高是很可观的。2 选择排序及其优化选择排序也是常用的排序方法之一,因为其排序过程简单实用,为众多的编程人员所喜欢,但是往往忽略进行优化 。211 选择排序的基本思想选择排序的基本思想是先从第一个位置起,依次和后

8、面的n - 1个数进行比较,找到一个最大值放在该位置,然后从第二个位置起,依次和后面的数进行比较,找到一个次大值放于第二个位置上,依此类推, n - 1轮以后即排序成功。此过程的进行,好像是在众多的待排元素选出一个符合条件的数放在该放的位置上,所以叫做选择排序。212 选择排序的C语言实现算法由选择排序的基本原理和图2中的排序过程,我们可以编写选择排序的一般算法如下。void selsort (int a ,int n)“int i ,j ,t ;/3t是用来作为中间交换变量3/for (i = 0 ;i n - 1 ;i + + )for (j = i + 1 ;j n;j + + )if

9、(ai aj )t = ai ;ai = aj ;aj = t ;此算法也是严格按照选择排序的过程来进行编写的,从这个算法,我们明显看出一个问题,就是在找某个位置上应该放置的数时,在没有真正找到该数前,有很多数要在此位置上占用一次,这就等于进行三次交换(算法中交换部分代码为三个赋值语句) ,所以我们可以看出,很多是没有必要的交换在这个算法里也进行了,这样肯定要影响程序的执行效率 。所以在排序过程中,我们要把这些无效的操作给去掉,比如找第一个位置上的数,如果比较过程中后面的数比该位置上的数大,先把这个数的位置记录下来,继续往后找;如果遇到比刚才记录的位置的数还要大,那么再记录该位置,一直找到最后

10、,就能够找到最大值的位置,然后一次性将该数和第一个位置上的数进行互换。依此类推,找第二个,第三个,第n - 1个 。由此,我们可以得出优化后的选择排序算法如下。213优化的选择排序优化后的选择排序算法如下。void optselsort (int a ,int n)inti ,j ,t ,p ;/3p用来记录第每一轮中最大值的位置3/for (i = 0 ;i n - 1 ;i + + )p = i ;/3p先初始化为待放的位置3/for (j = i + 1 ;j n;j + + )if (a p aj )/3 如果位置p上的数小于后面的数,更改p的值 3/p = j ;if (p != i

11、)/3 如果p != i说明,最初p所代表的那个位置上的值不是最大值3/t = ai ;ai = ap ;ap = t ;此算法中, p就是专门用来记录最大值位置的一个变量 。最初的值是待放的位置,找到比较大的值, p就将该位置记录下,一直找到最后。如果p的值改变了,即不等于待放元素的位置(i)了,说明后面有比该位置上数大的数,而且是后面序列中最大的数,所以最后将其交换。如果p的值一直没有发生变化,说明该位置上数即为符合条件的数,不用交换,继续下一轮选择。以此算法,从而实现了选择排序的优化 。3插入排序及其优化插入排序也是程序设计中常用的排序方法,在生活中用的非常多,我们平时生活中部会自觉不自

12、觉地用到该方法进行排序 。22200712九 江 职 业 技 术 学 院 学 报Journal of Jiujiang Vocational& Technical College名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 3 页 - - - - - - - - - 311 插入排序的基本思想插入排序的基本思想,是将一个数插入到一个已经排好序的序列 。这里面关键的问题是,已经排好序的序列怎么选?如果一个待排的序列,怎么去找一个已经有序的序列?其实这个过程很简单,我们只需

13、要选择第一个数作为一个已经排好序的序列就可以了。312 插入排序的C语言算法由插入排序的基本原理和图3中的排序过程,我们可以得出插入排序的一般算法。void insertsort (int a ,int n)inti ,j ,t ;for (i = 1;i 0;j - )/3 插入的过程从后向前,所以j的值最大到小,步长为13/if (aj - 1 aj )/3 前面的数小于后面的数,则进行交换 3/t = aj - 1 ;aj - 1 = aj ;aj = t ;该算法也是按照插入排序的过程来编写的。插入排序是在原来无序的数组中进行,先找到一个己排好的序列(通常选取第1个数作为已经排好序的序

14、列)。然后依次拿后面待插入的数,在已排好序的序列中从后向前依次比较、交换,最后找到该数应该插入的位置。这个过程,我们可以叫做试探法,也就是依次试探着去找最后应该插入的位置,然后再往前面进行比较试探,一直找到应该插入的位置。由此可见,这是一个基于交换的插入排序。而真正的插入排序是应该找到插入的位置,然后腾出位置,再将待插入的数据一次性地放入到该位置。具体实现算法如下 。314 插入排序的优化根据上面所讲的优化方法,我们用C语言写出其实现的算法 。void optinssort (int a ,int n)inti ,j ,t ;for (i = 1 ;i = 0 & &t aj /3 待插入的元

15、素比前面的元素均小或已经找到插入位置3/aj + 1 = aj ;j -;aj + 1 = t ;此算法,我们可以看出尽管没有节省比较的次数,但是节省了交换的次数。没有优化的算法是基于交换的插入排序,而现在我们进行的是先找其插入的位置。找的时候,让一些该移动的数往后移去腾出位置,找到要插入的位置时,位置也刚好腾出来了,然后我们再将待插入的数据直接放置到该位置上即可。其它排序的算法,实现起来也有很多方法,但是在实现这些算法的时候,一定要考虑到排序过程中的优化,不要让系统去做一些无为的操作,从而把程序执行次数减少到必不可少的地方,让我们的程序运行效率更高。在这里,对其它排序方法,我们就不再这里探讨

16、,读者可以借鉴以上这些算法去分析实现。参 考 文 献1丁爱萍等1C语言程序设计实例教程 M 1 西安:电子科技大学出版社, 200412谭浩强1C程序设计(第二版) M 1 清华大学出版杜, 1999 , 1213严蔚敏,吴伟民1数据结构C语言版 M 1 清华大学出版社, 1997 , 414田淑清 1 计算机等级考试二级C语言教程 M 1 北京:高等教育出版社, 1998 , 915李玲等1C语言程序设计 M 1 北京:人民邮电出版杜, 2005 , 21Sorting and Optimizationin Program DesigningDUHengL I Huai - gangCHEN

17、Ping(Henan PolytechnicInstitute, Nanyang , Henan , 473009 )Abstract : Sorting is a very importantoperation in the programdesigning.There is the functionof sorting inmany soft wares.Sorting is also the importantfactor which influences the efficiency of the programrunning.Thedesigning of sorting modul

18、e directly influences the performance of the whole program.This article deeply discussesthe realization and optimizationof widely used three kinds of sorting methods.Key words : Program designing , Sort , Running efficiency32200712九 江 职 业 技 术 学 院 学 报(杜恒 : 程序设计中的排序及优化)名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 3 页 - - - - - - - - -