5.3 排序算法的程序实现 课件（22张幻灯片）

课件22张PPT。排序算法的程序实现第五章 算法实例的程序实现冒泡排序基本原理： 在一列数据中把较小的数据逐次向上推移的一种排序技术。 把待排序的n个元素的
数组看成是垂直堆放的一列数据，从最下面的一个元素起，自下而上的比较相邻的两个元素中的数据，将较小的数据换到上面的一个元素中。 重复这一过程，直到处理完 最后两个元素中的数据，称为一遍加工。当第一遍加工完成时，最小的数据已经上升到到第一个元素的位置。 然后对余下的n-1个元素重复上述处理过程，直至最后进行余下两个数据的比较与交换。由于每一遍加工都是将本遍最小的元素像气泡一样上浮至本遍的顶端位置，故称为冒泡排序。d(1) d(2) d(3) d(4) d(5)冒泡排序算法的程序实现第一趟排序 8 14 11 13 9原始数据 14 11 13 8 9If d(5)If d(j)If d(j)Next jFor j=5 to 4 step -1
If d(j)Next jFor j=5 to 5 step -1
If d(j)Next jFor i=1 to n-1

Next iIf d(j)交换
EndIf
For j=n to i+1 step -1

Next j两个数的交换 有两个杯子，A杯装满了可乐，B杯装满了雪碧，如何交换A杯和B杯中的饮料？A=3
B=6
如何用程序实现将A和B中的
内容交换一下？K=A
A=B
B=K点击输标For i=1 to n-1
For j=n to i+1 step -1
If d(j)K=d(j):d(j)=d(j-1):d(j-1)=k
EndIf
Next j
Next i冒泡排序的核心代码1.要进行 轮冒泡如果要对有5个元素的数组进行排序，那么： 42.第一轮冒泡的时候它进行比较的范围是
从 到 。3.第二轮冒泡的时候它进行比较的范围是
从 到 。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)1.要进行 轮冒泡 如果要对有n个元素的数组进行排序，那么： n-12.外循环变量i从 到 变化
1 n-13.内循环变量j从 到 变化
n i+1 1.冒泡排序：每次从最下面的元素开始，通过逐次往上比较，将较小的数向上推移 2.如果有n个数组的元素进行排序，则要进行n-1趟冒泡 第一趟冒泡要经过n-1次比较 第二趟冒泡要经过n-2次比较 …… 第n-1趟冒泡要经过1次比较 总计要经过:(n-1)+(n-2)+(n-3)+………+2+1次比较冒泡排序小结：冒泡排序算法？第二章 算法实例优点：算法简洁明了，便于编程实现不足：交换次数频繁，程序执行时间长选择排序基本原理： 是对冒泡排序算法
的改进。 在参加排序数组的所有元素中找出最小数据的元素，使它与第一个元素中的数据相互交换位置。
然后再余下的元素中找出最小数据的元素，与第二个元素中的数据相互交换位置。 以此类推，直到所有元素成为一个有序的序列。由于排序过程中，交换的次数比冒泡排序小，因此它具有较高的效率。d(1) d(2) d(3) d(4) d(5)选择排序算法的程序实现第一趟排序 8 11 13 14 9原始数据 14 11 13 8 9If d(2)If d(3)If d(4)If d(5)If d(j)k then
m=d(i):d(i)=d(k):d(k)=m
EndIfd(1) d(2) d(3) d(4) d(5)选择排序算法的程序实现第二趟排序 8 9 13 14 11原始数据 14 11 13 8 9For j=3 to 5
If d(j)k then
m=d(i):d(i)=d(k):d(k)=m
EndIfIf d(3)If d(4)If d(5)If d(5)If d(j)k then
m=d(i):d(i)=d(k):d(k)=m
EndIfd(1) d(2) d(3) d(4) d(5)选择排序算法的程序实现第二趟排序 8 9 13 14 11原始数据 14 11 13 8 9第一趟排序 8 11 13 14 9第三趟排序 8 9 11 14 13第四趟排序 8 9 11 13 14k=4 If d(5)If d(j)k then
m=d(i):d(i)=d(k):d(k)=m
EndIf点击输标For i=1 to n-1
k=i
For j=i+1 to n
If d(j)Next j
If i<>k then
m=d(i):d(i)=d(k):d(k)=m
EndIf
Next i选择排序的核心代码数据元素a(1)到a(5)的数据依次为
“10，41，75，12，63，”，
则此程序运行完成后数组元素
a(1)到a(5)的数据依次是（ ）
A.75，63，41，12，10
B.10，12，41，63，75
C.10，12，75，41，63
D.75，63，10，12，41
某一段程序段如下：
For i=1 to 2
k=i
For j=i+1 to 5
if a(j)>a(k) then k=j
next j
if i<>k then
t=a(i)
a(i)=a(k)
a(k)=t
EndIf
Next i
问题探究以对n个元素的数组进行排序，那么：(n-1)+…+3+2+1(n-1)+…+3+2+1<=(n-1)*n/2<=(n-1)