例9.9:冒泡排序算法。
1.排序方法
为了描述方便,下面R数组的下标从1开始,共n个元素。
将被排序的记录数组R[1..n]垂直排列,每个记录R[i]看作是重量为R[i]的气泡。根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R,凡扫描到违反本原则的轻气泡,就使其向上"飘浮"。如此反复进行,直到最后任何两个气泡都是轻者在上、重者在下为止。冒泡排序过程,如图9.10所示。
(1)初始
初始状态:R[1..n]为无序区。
图9.10 冒泡排序过程例图(一)
(2)第一次扫描
从无序区底部向上依次比较相邻的两个气泡的重量,若发现轻者在下、重者在上,则交换二者的位置。即依次比较(R[n],R[n-1]),(R[n-1],R[n-2]),…,(R[2],R[1]);对于每对气泡(R[j+1],R[j]),若R[j+1]<R[j],则交换R[j+1]和R[j]的内容。
第一趟扫描完毕时,"最轻"的气泡就飘浮到该区间的顶部,即值最小的纪录被放在最高位置R[1]上。
(3)第二次扫描
扫描R[2..n]。扫描完毕时,"次轻"的气泡飘浮到R[2]的位置上……
最后,经过n-1趟扫描可得到有序区R[1..n]。
第i次扫描时,R[1..i-1]和R[i..n]分别为当前的有序区和无序区。扫描仍是从无序区底部向上直至该区顶部。扫描完毕时,该区中最轻气泡飘浮到顶部位置R[i]上,结果是R[1..i]变为新的有序区。
图9.11 冒泡排序过程例图(二)
2.实现参考代码:
运行结果如图9.12所示。
图9.12 例9.9程序运行结果
在本章中,我们主要学到了如下知识点:
➢为什么使用数组?为了程序操作的方便,需要将一组相关的数值存储在一起,单个变量不能满足需求,而数组可以。
➢数组是一组有序的、类型相同的数据的集合。
➢数组的存储机制:
·数组元素具有相同数据类型。
·在内存中,数组均由连续的存储单元组成。
➢一维数组名[下标]就可以引用一维数组元素。
➢数组名的含义:始终代表数组的首地址,是一个常量。(www.xing528.com)
➢初始化数组有三种方法。
➢简单字符串的应用:输入输出字符串。
➢冒泡排序的原理:根据轻气泡不能在重气泡之下的原则,从下往上扫描数组:凡扫描到违反本原则的轻气泡,就使其向上"飘浮"。如此反复进行,直到最后任何两个气泡都是轻者在上、重者在下为止。
1.某百货商场当日消费积分最高的8名顾客,他们的积分分别是:18,25,7,36,13,2,89,63,从这组数中找出最少的积分数以及它在数组中的原始位置,运行效果如图9.13所示。
图9.13 输出积分最少的数及在数组中的位置
2.从键盘输入本次C语言考试的5个学生的成绩,找出其中的最高分,运行效果如图9.14所示。
图9.14 输出最高分
3.小强从超市购买了10件商品,编写一个程序,用于接收每件商品的价格,计算应付的总金额并输出,运行效果如图9.15所示。
图9.15 计算商品总价格
4.计算5位学生的平均成绩并输出(提示:首先定义一个数组存储5位学员的成绩,然后计算平均值),运行效果如图9.16所示。
图9.16 输出五位学生的平均成绩
5.定义一个数组,数组一共有10个元素,接收用户输入的值,求出下标为偶数的元素值之和,运行效果如图9.17所示。
图9.17 求下标为偶数的元素之和
6.定义一个数组,数组一共有10个元素,接收用户输入的值,将数组元素从高到低排序后输出,运行效果如图9.18所示。
图9.18 数组元素排序
1.接收用户输入的一个6位数字,将这个6位数字按逆序输出。例如输入:123456,输出:654321。(提示:分解这个数字的个位、十位...十万位,存放到数组中,将数组元素逆序输出)运行效果如图9.19所示。
图9.19 将数字按逆序输出
2.输入一个年份和月份,输出这月有多少天?(提示:用一个数组存放一年12个月的天数)运行效果如图9.20所示。
图9.20 输出这月有多少天
3.输入一个日期,输出这个日期是这年的第几天?(提示:用一个数组存放一年12个月的天数)运行效果如图9.21所示。
图9.21 输出这个日期是这年的第几天
4.利用随机数生成一个整数数组,数组中有10个元素,每个元素的值在0-9之间,打印该数组的每个元素,运行效果如图9.22所示。
图9.22 输出数组中的值
5.有一个包含10个元素的数组,元素的值分别为:10,20,30,40,50,60,70,80,90,100,求出:第一个元素-第二个元素+第三个元素-第四个元素+第五个元素-第六个元素+第七个元素-第八个元素+第九个元素-第十个元素=?运行效果如图9.23所示。
图9.23 输出计算结果
免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。