排序是程序设计中非常重要的内容,它的功能是将一组无序的的数据,排列成有序的数据序列,经过排列后的数据,要么是从大到小排列,要么是从小到大排列。一般也只有这两种情况。
例如我们统计班级学生的成绩,那么一般是按照学号来进行统计,原来成绩是无序排列的,这样的话非常不适合于我们对成绩的查询,那么一般我们进行成绩查询之前,先进行排序,如按照高分到低分的排序,这样可以很快地查出本班的最高分和最低分,和成绩比较靠前或靠后的学生。
排序有很多种方法,常用的有三种:冒泡排序、选择排序、插入排序等,下面我们就对这三种方法做一下分析和比较,以便大家能够更好的理解和应用。
一、冒泡排序
1、冒泡排序的基本思想:对于n个数进行排序(现假定是从大到小排序,以下均按此进行),将相邻两个数依次比较,将大数调在前头:也就是说第一个数和第二个数比较,大数放前,小数放后,第二个和第三个进行比较,大数放前、小数放后,然后依次类推。。。经过第一轮比较以后,我们找到一个最小数在最下面(沉底)。然后进行下一轮比较,最后一个数就不用再参加比较了,所以本轮就可以少比较一次。
很显然,需要用双重循环来设计这个问题,外层循环控制进行的轮数,内层循环控制每轮比较的次数,那么到底需要多少轮、每轮需要多少次,我们通过一个实例看一下:
2、排序过程举例:
外循环
1轮
2轮
3轮
4轮
内循环
5个数比较4次
4个数比较3次
3个数比较2次
2个数比较1次
7
5
8
6
9
1次
2次
3次
4次
1次
2次
3次
1 次
2次
1次
7
5
8
6
9
7
8
5
6
9
7
8
6
5
9
7
8
6
9
5
8
7
6
9
5
8
7
6
9
5
8
7
9
6
5
8
7
9
6
5
8
9
7
6
5
9
8
7
6
5
最小的数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;}
} |