冒泡排序算法
株洲市第二中学 信息技术组
刘辉琴 杜新宇
活动： 按照计算机的工作方式将下面一组无序的 将下面一组无序的数据从小到大排列。 数据从小到大排列。 { 49,38,65,97,76,13,27,49 } 数据如何存储？ ——一维数组
定义一维数组： int r[8]； 数组元素为： r[0], r[1], r[2], r[3], r[4], r[5], r[6], r[7]
冒泡排序 选择排序
插入排序
……
小结：
1、冒泡排序的基本原理、算法流程图及 程序实现。 2、一维数组 3、双重循环
main() { int r[8];int i,j,t; printf("Input 8 numbers:\n"); for(i=0;i<8;i++) scanf("%d",&r[i]); for(j=0;j<7;j++) for(i=0;i<7-j;i++) if(r[i]>r[i+1]) {t=r[i]; r[i]=r[i+1]; r[i+1]=t;} printf("The sorted numbers:\n"); for(i=0;i<8;i++) printf("%4d",r[i]); system("pause"); }
r[0]>r[1]
第一步做什么？ if ( 否 {
)
如何交换数据？ } r[1]>r[2] 否 有没有办法让流程图更 加简洁呢？ 不断的这样画下去要画多少个 类似的选择结构？
…
二.画出第一趟排序的算法流程图： 用简洁的循环结构进行表示 根据流程图完善程序：
开始
i=0
是 t=r[ i] t=r[0] r[ ir[0]=r[1] ] =r[i +1] R[1]=R[2] tt r[ir[1]= +1] = r[r[0]>r[1] i ]>r[i +1] 否
4 ห้องสมุดไป่ตู้7 4 76 4 13 4 27 4 49 4 49 4 49 4 49
5 76 5 13 5 27 5 49 5 49 5 49 5 49 5 49
6 13 6 27 6 49 6 65 6 65 6 65 6 65 6 65
7 27 7 49 7 76 7 76 7 76 7 76 7 76 7 76
第一趟排序后的数据和序号 序号 数据 0 38 1 49 2 65 3 76 4 13 5 27 6 49 7 97
第二趟排序的步骤： 序号 数据 0 38 1 49 2 65 3 76 13 4 13 76 27 5 27 76 49 6 49 76 7 97
65 <76, 保持不变 49<65, 保持不变 76>13, 76>27, 交换位置 交换位置 76>49, 76<97, 交换位置 保持不变 38<49, 保持不变
那么同样的结构要进 行多少次呢？ i++
有没有办法让流程图更 加简洁呢？
是
i <=5
否 结束
三：画整个冒泡排序的流程图。 分析：这是一个两重循环结构。
是
t=r[i ] r[i ]=r[i +1] r[i +1]= t
开始
j=0 i=0
r[i ]>r[i +1] 否
i++
是
i <=？
否
是
j++ j<=6
for( ; if ( {
; )
)
i++
是
}
i <=6
否 结束
按照这种画法第二趟、第三趟、第四趟排序的流程图 怎样画？怎样把整个冒泡排序的流程图画出来？
开始
i=0
是 R[1]>R[2] r[ i ]>r[i +1] 否
分析：后面的排序只要 按照这种方法不断进行就 行了。
t=r[i ] t=R[2] r[ i ]=r[i +1] R[1]=R[2] R[2]= tt r[ i +1]=
为了方便分析，我们把数组r中的元素先 用一个表格列出来，如下：
原数据和序号
序号
数据
0
49
1
38
2
65
3
97
4
76
5
13
6
27
7
49
第一趟排序的步骤： 序号 0 1 2 3 4 5 6 7
数据
49 38
38 49
65
97 76
76 97 13
13 97 27
27 97 49
49 97
97>49, 交换位置 49<65, 65<97, 保持不变 保持不变 97>76, 97>13, 交换位置 97>27, 交换位置 交换位置 49>38, 交换位置 对比原数据经过第一趟排序，实现了什么目的？ 第一趟排序，一共进行了多少次比较？
初始
序号 数据 序号 数据 序号 数据 序号 数据 序号 数据 序号 数据 序号 数据 序号 数据
1 49 1 38 1 38 1 38 1 38 1 13 1 13 1 13
2 38 2 49 2 49 2 49 2 13 2 27 2 27 2 27
3 65 3 65 3 65 3 13 3 27 3 38 3 38 3 38
否 结束
开始
输入数据
j=0 i=0 是 r[i]>r[i+ 1]
否
t=r[i ] r[i ] =r[i +1] r[i +1] = t
i++
main() { int r[8]; int i,j,t; printf("Input 8 numbers:\n"); for(i=0;i<8;i++) scanf("%d",&r[i]); for( ; ; ) for( ; ; ) {
8 49 8 97 8 97 8 97 8 97 8 97 8 97 8 97
1趟
2趟
3趟 4趟
5趟
6趟 7趟
描述算法：
试着将我们刚才排序的全过程用算法流 程图表示出来。
我们把它分成几步来做。
一.画出比较r[0]与r[1] 的算法流程图： 分析：
是 t=r[0] r[0] =r[1] r[1] = t 继续： 是 t=r[1] r[1] =r[2] r[2] = t 开始 根据流程图完善代码：
i<=6-j
j++
j<=6
输出数据 结束
} printf("The sorted numbers:\n"); for(i=0;i<8;i++) printf("%5d",r[i]); system("pause"); }
冒泡排序
基本思想：
对相邻两个数进 行比较，将较小的调 到前面，两两比较一 轮之后，最大的一个 数被放置在最后面； 接着从头开始重复执 行以上操作，次大的 数被放置在倒数第二 位，依次类推，数列 由后往前逐渐成型。
经过第二趟排序，实现了什么目的？
观察原数据与第一、二趟排序后的数据 序号 数据 序号 0 49 0 1 38 1 2 65 2 3 97 3 4 76 4 5 13 5 6 27 6 7 49 7
数据
序号
38
0
49
1
65
2
76
3
13
4
27
5
49
6
97
7
数据
38
49
65
13
27
49
76
97
我们预计最多一共要经过多少趟排序呢？