有十个数:10,9,8,7,6,5,4,3,2,1 。将他们按从小到大的顺序排成一列,用这两种方法的区别在于如下过程中:
1、 冒泡排序:
外层循环一共进行9次,第一次将10排到最后,这一步要经很9步交换清慧樱,即将10依次和9,8,7……交换,成为如下顺序:9,8,7,6,5,4,3,2,1,10;接着第二次将9排到倒数第二,这一步要经过8步交换,变成如下顺序:8,7,6,5,4,3,2,1,9,10同理执行共九大步,即可将它们最终排成1,2,3,4,5,6,7,8,9,10。
从这个过程可以看到,这种方法在这个过程中一共进行了9+8+7+6+5+4+3+2+1=45次比较和交换。
2、 选择排序:
外层也要经过9次大步,但是不用交换45次.首先要假定一个最大量假设是第一个,并用max标记,第一次,将10依次和9,8,7,6,5,4,3,2,1进行比较,但是只是和1进行了一次交换,这时数列成了:1,9,8,7,6,5,4,3,2,10;第二次:将1和9比较,发现9比较大,那么将9暂时定为最大max,再依次和8,7,6,5,4,3,2比较,最答丛后发现9最大,就把9和倒数第二个位置上的2交换,这一大步共进行了两次交换;依次执行下去,后面每大步进行了两次交换,可以看出,一共进行了1+2+2+2+2+2+2+2+1=16次交换,但是也进行了45次比较。
从上面两种可以看出,这两个方法选择排序更高速,但是某些数据可能使得冒泡排序更高速,即交换次数较少,可以看出算法快慢和数据还是有一定关系的。
至于代码,我写了一个选择排序法的,c++环境运行通过:
将代码复制后在编辑窗口选定内容按下Alt+F8可以快速对齐格式:
#include<stdio.h>
#include<time.h>/*包含时间函数,以便作为随机数种子*/
#include<stdlib.h>/*包含产生随机数的文件*/
void main()
{
int i,j,temp,max
int a[10]
srand((unsigned)time(NULL))/*作用是可以每次产生不一样的随机碧雹数*/
for(i=0i<10i++)
{
a[i]=rand()%51+49
}
for(i=0i<10i++)
{
printf("a[%d]=%2.0d\t\t",i+1,a[i])/*控制格式*/
}
printf("\n")
for(i=0i<10i++)
{
temp =a[10-i]max=10-i/*设定最大值*/
for(j=0j<10-ij++)
{
if(a[j]>temp)
{
temp =a[j]max=j/*更新最大值*/
}
}
if(max!=10-i)
{
a[max]=a[10-i]a[10-i] = temp/*不能忘记将找到最大值处用假设最大值补上!*/
}
}
for(i=0i<10i++)
{
printf("a[%d]=%d\t\t",i+1,a[i])
}
}
没有写冒泡法的,相信你也能写了。写了这么久,希望得个辛苦分。
另外有问题随时问。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)