排序有很多种方法,常用的有三种:冒泡排序、选择排序、插入排序等,下面我们就对这三种方法做一下分析和比较,以便大家能够更好的理解和应用。
一、冒泡排序
1、冒泡排序的基本思想:对于n个数进行排序(现假定是从大到小排序,以下均按此进行),将相邻两个数依次比较,将大数调在前头:也就是说第一个数和第二个数比较,大数放前,小数放后,第二个和第三个进行比较,大数放前、小数放后,然后依次类推。。。经过第一轮比较以后,我们找到一个最小数在最下面(沉底)。然后进行下一轮比较,最后一个数就不用再参加比较了,所以本轮就可以少比较一次。
很显然,需要用双重循环来设计这个问题,外层循环控制进行的轮数,内层循环控制每轮比较的次数,那么到底需要多少轮、每轮需要多少次,我们通过一个实例看一下:
2、排序过程举例:
外循环
1轮
2轮
3轮
4轮
内循环
5个数比较4次
4个数比较3次
3个数比较2次
2个数比较1次
最小的数5沉底,其余4个数继续比较
次小数6沉底,其余3个数
7沉底,其余2个数比较
最后两个数一次比较
那么通过这个排序过程,我们了解了怎样去进行排序,那么到底谁是气泡呢,我们可以从中找出答案,那么从大到小进行排序,较大的一些数就是气泡。随着排序的进行,气泡逐步上升。
从这个排序过种中,还可以看出,5个数实际经过4轮就可以了,实践证明,n个数最多需要n-1轮排序就可以了。
3、冒泡排序的程序如下:
for(i=0;i<10;i++)
for(j=0;j<10-i;j++)
if(a[j]<a[j+1])
{t=a[j];a[j]=a[j+1];a[j+1]=t;}
在此程序段的上面加上输入部分和在程序段加上排序后的输出。
程序的改进:
4、算法的改进:
从上面的排序的过程可以看出,如果一个已经排好序的一组数或者经过很少的轮数就可以排完这些数,但是循环还是要继续进行,这样设计出的程序浪费了大量的时间,所以对一这个算法我们可以重新设计。
经过修改后的程如下:
for(i=0;i<10&&!swap;i++)
{
swap=1;
for(j=0;j<10-I;j++)
if(a[j]<a[j+1])
{t=a[j];a[j]=a[j+1];a[j+1]=t;swap=0;}
}
二、选择排序
1、排序的基本思想:先从第一个数开始起,用第一个数和其它的数进行比较,如果比第一个数大就交换位置,否则不进行交换,这样经过第一轮比较我们就能够找出最大值放在第一位置,然后从第二个位置起再找次大数,这样依次下去,就可以进行整个数的排序,实践证明,n个数最多需要n-1轮排序就可以了。
2、排序过程举例:
外循环
1轮
2轮
3轮
4轮
内循环
5个数比较4次
4个数比较3次
3个数比较2次
2个数比较1次
最大的数9找到,其余4个数找次大数
次大数8找到,其余3个数找
7找到,其余2个数找
最后两个数一次比较
选择排序较冒泡容易理解,程序编写也要相对容易一些。---www.bianceng.cn
for(i=0;i<10;i++)
for(j=i+1;j<10;j++)
if(a[i]<a[j])
{t=a[i];a[i]=a[j];a[j]=t;}
对于选择排序,我们也可以看到一个问题,如第一轮排序中,我们要找的是9才是最大值,所以其它的交换完全没有必要进行,其它各轮都存在这样的情况,所以我们可以想办法取消这种情况,也就是说我们真正找到的最大值的位置后再进行交换。
for(i=0;i<10;i++)
{ p=i;
for(j=i+1;j<10;j++)
if(a[p]<a[j])
p=j;
if(p!=i)
{t=a[i];a[i]=a[j];a[j]=t;}
}
这样算法经过改进以后就较好地解决了这个问题。
分享到:
相关推荐
多窗口快速排列方法、多窗口快速排列系统及移动装置.zip
篮球单循环比赛排列方法.pdf
电信设备-一种操作菜单排列方法及移动终端.zip
行业资料-交通装置-一种交通工具座位排列方法.zip
电信设备-一种图标的排列方法、装置及移动终端.zip
行业文档-设计装置-一种换热装置中传热管的排列方法
行业分类-设备装置-一种面向3D打印的模型分解与排列方法
电子政务-印刷电路板钻孔机或成型机钻轴的排列方法.zip
行业分类-电子-基于大功率转换潮汐能的发电机排列方法的说明分析.rar
行业文档-设计装置-纸烟或雪茄烟在装烟时每支烟在烟盒内的排列方法.zip
正交排列测试方法 正交排列测试方法 正交排列测试方法 正交排列测试方法 正交排列测试方法
吧数组从小到大排列 用于一维数组 - - 二维数组还不会写 高手路过吧
研究局部切空间排列方法(LTSA)对离群点的敏感性,提出一种基于离群点检测的鲁棒局部切空间排列方法( RLTSA).该方法用样本点到切空间的投影距离检测离群点.在构造样本点局部邻域时,RLTSA尽可能排除离群点,以构造稳定的...
在此基础上,探讨了原型理论以及该理论在词典义项排列中的应用,指出借鉴原型理论能对义项排列起到一定的优化作用,可以作为其他排列方法的一种补充。在肯定原型义项排列法优点的同时,还讨论了其不足之处,其中最重要的...
对经典算法中全局信息和局部信息的提取机制进行分析后,提出一种邻域线性竞争的排列方法(neighborhood linear rival alignment algorithm,NLRA)。通过对数据点的近邻作局部结构提取,有效挖掘稀疏数据内部信息,...
为了评价利用等螺旋升角进行截齿排列设计的截割头的截割性能,选用了一个实际的截割头进行比较,通过计算机仿真获得两个...载荷大小及其波动较小,截割性能良好,所以用等螺旋升角排列截齿是一种高效、实用的截齿排列方法。
针对已有的OSPF路由选择协议作进一步的研究,分析并运用了数学原理中的禁位排列方法,设计出一种新的路由决策算法。研究表明,路由单链排列状态下,该算法与Dijkstra算法具有相同的时间复杂度;在实际网络结构下,...