1、冒泡排序专题复习冒泡排序的思想从最下面一个元素起，依次比较相邻的两个元素中的数据，将较小的数据调换到上面，小元素像气泡一样上浮。如何实现将较小数逐次从下向上推移呢？冒泡排序的过程12345设置数组变量：a(i)为牌的值（i=1、2、3、4、5)第一轮冒泡12345a(5)a(4)，不交换 a(4)a(3)，交换 a(3)a(2),交换 a(2)a(4)，不交换 a(4)a(3)，不交换 a(3)a(4)，交换 a(4)a(3)，不换 第四轮冒泡12345a(5)a(4)，交换 分析与总结如果要对有5个元素的数组进行排序，那么 1、要进行_轮冒泡 2、第一轮冒泡，比较的范围从 到 ；第二轮冒泡，
2、比较的范围从 到 ；第三轮冒泡，比较的范围从 到 ；第四轮冒泡，比较的范围从 到 。3、总比较次数 次，数据最多交换 次。4 a(5)与a(4)a(2)与a(1)a(5)与a(4)a(5)与a(4)a(5)与a(4)a(3)与a(2)a(4)与a(3)a(5)与a(4)10 10 提高如果要对有n个元素的数组进行排序，那么 1、要进行_轮冒泡 2、第一轮冒泡，比较的范围从 到 ；第二轮冒泡，比较的范围从 到 ；第三轮冒泡，比较的范围从 到 ；第n-1轮冒泡，比较的范围从 到 。3、总比较次数 次，数据最多交换 次。a(2)与a(1)a(3)与a(2)n-1 a(n)与a(n-1)a(n)与a(
3、n-1)a(n)与a(n-1)a(n)与a(n-1)a(n)与a(n-1)a(4)与a(3)n(n-1)/2 n(n-1)/2 冒泡排序程序实现For i=1 to n-1 For j=n to i+1 step-1 If a(j)a(j-1)思考：若从前往后实现大值“下沉”，程序如何修改？For i=1 To n-1 For j=If a(j)a(j-1)Then t=a(j):a(j)=a(j-1):a(j-1)=t End If Next j Next i 2 to n-i+1 思考：若从前往后实现大值“下沉”，程序如何修改？For i=n To 2 step-1 For j=If a(
4、j)a(j+1)Then t=a(j):a(j)=a(j+1):a(j+1)=t End If Next j Next i n-1 To i Step-1 思考：若只需要寻找数组中最大的三个数，程序如何修改？For i=For j=n To i+1 Step-1 If Then t=a(j):a(j)=a(j-1):a(j-1)=t End If Next j List1.AddItem Str(a(i)Next i a(j)a(j-1)1 to 3a(j-1)a(j)思考：若只需要将数组x到y位置的元素进行排序（1=x=y=n),程序如何修改？(考虑排序不同方向）For i=1 to y-x
5、 For j=x+1 to y-i+1 If a(j)a(j-1)Then t=a(j):a(j)=a(j-1):a(j-1)=t End If Next j Next i y to x+i step-1 2.有如下VB程序段：For i=1 To 2 For j=5 To i+1 Step-1 If a(j)a(j-1)10 Then t=a(j):a(j)=a(j-1):a(j-1)=t End If Next j Next i 执行完该程序段后，下列选项中，a(1)到a(6)各元素的值可能是 A.84,98,93,84,62,30 B.70,60,10,28,18,14 C.34,44,
6、36,14,16,94 D.77,42,34,16,24,82 C总结IF语句条件表达式即为排序的条件，按照什么内容（关键字）排序，排成什么状态（升序或者降序）。内层循环：循环变量范围控制参与排序元素的范围，全部参与还是部分参与，步长控制数据比较的方向，前面先有序还是后面先有序。外层循环：循环变量范围控制冒泡的个数，完全冒泡还是部分冒泡。程序优化：n个数不一定需要冒n-1个泡才完全有序，比如数组“3，5，7，9，11，2”冒一个泡后就实现了完全有序。如何实现一旦发现数组数据已经有序程序就不再进行排序，从而提高程序效率？思考：如何判断一个数组数据已经有序了？flag=False:i=1 Do W
7、hile in and flag=False flag=True For j=n To i+1 Step-1 If a(j)a(j-1)Then t=a(j)a(j)=a(j-1)a(j-1)=t flag=False End If Next j i=i+1 Loop 某一轮冒泡过程没有发生数据交换，则说明数组有序4.有以下VB程序：flag=True:i=1:n=6 Do While i=n-1 and flag=True flag=False For j=n To i+1 Step-1 If a(j)a(j-1)Then t=a(j)a(j)=a(j-1)a(j-1)=t flag=Tru
8、e End If Next j i=i+1 Loop 有一数组a(1 to 6)，其数值分别为“45，39，78，37，93，64”，想要按照从小到大排序，执行完该程序段后，数据总比较次数和总交换次数分别是 A.9次和4次 B.9次和6次 C.12次和6次 D.15次和12次 C程序变式一：数组a(1 to 8)10 5 8 6 9 4 15 9 原序列：数组a(1 to 8)4 5 6 8 9 9 10 15 排序后：For i=1 To n 2 For j=n-i+1 To i+1 Step-1 If a(j)a(j-1)Then t=a(j):a(j)=a(j-1):a(j-1)=t N
9、ext j For j=i+2 To n-i+1 Step 1 If a(j)a(j-1)Then t=a(j):a(j)=a(j-1):a(j-1)=t Next j Next i 变式扩展：数组a(1 to 8)10 5 8 6 9 4 15 9 原序列：数组a(1 to 8)4 5 6 8 9 9 10 15 排序后：For i=1 To n 2 For j=i+1 To n i+1 Step 1 If a(j)a(j-1)Then t=a(j):a(j)=a(j-1):a(j-1)=t Next j For j=n-i To i+1 Step-1 If a(j)a(j-1)Then t
10、=a(j):a(j)=a(j-1):a(j-1)=t Next j Next i 变式扩展：数组a(1 to 8)10 5 8 6 9 4 15 9 原序列：数组a(1 to 8)4 6 9 10 15 9 8 5 排序后：For i=1 To n 2 For j=n-i+1 To i+1 Step-1 If a(j)a(j)Then t=a(j):a(j)=a(j+1):a(j+1)=t Next j Next i 程序变式二：数组a(1 to 8)10 5 8 6 9 4 15 9 原序列：数组a(1 to 8)4 15 5 10 6 9 8 9 排序后：k=1 For i=1 To n-
11、1 For j=n To i+1 Step-1 If a(j)*k a(j-1)*k Then t=a(j):a(j)=a(j-1):a(j-1)=t End If Next j k=-k Next i 程序变式三：数组a(1 to 8)10 5 8 6 9 4 15 9 原序列：数组a(1 to 8)8 4 9 5 10 6 15 9 排序后：For i=1 To(n 1)2 For j=1 To n-2*i If a(j)a(j+2)Then t=a(j):a(j)=a(j+2):a(j+2)=t End If Next j Next i 变式扩展：数组a(1 to 8)10 5 8 6
12、9 4 15 9 原序列：数组a(1 to 8)15 4 10 5 9 6 8 9 排序后：k=1 For i=1 To(n-1)2 For j=1 To n-2*i If a(j)*k a(j+2)*k Then t=a(j):a(j)=a(j+2):a(j+2)=t End If k=-k Next j Next i 5.有如下VB程序段：k=1 For i=1 To 2 For j=1 To 6-2*i If k*a(j)k*a(j+2)Then t=a(j):a(j)=a(j+2):a(j)=t End If k=-k Next j Next i 数组元素a(1 to 6)的初始 数值分别为“15，11，58，38，26，9”，执行完该程序段后，数据a元素的值分别是 A.58，9，26，11，15，38 B.58，38，26，11，15，9 C.15，38，26，11，58，9 D.58，38，26，15，11，9 A