浙教版信息技术选修1 2.3 选择排序课件（共17张ＰＰＴ）

课件17张PPT。选择排序一：什么是选择排序（selection sort）选择排序是对冒泡排序算法的改进，在参加排序的所有数组元素中找出最小数据的元素，使它与第一个元素中的数据相互交换位置。然后再在余下的元素中找出最小数据的元素，与第二个元素中的数据相互交换位置，以此类推，直到所有元素成为一个有序的序列。此方法中交换的次数比冒泡排序少，具有较高的效率。选择排序的实现过程a(1)a(2)a(3)a(4)a(5)i=1(用变量i表示第一遍处理，也表示第一个数据元素)
在第1至第5个数组元素中找最小数据 (最小数据的下标用变量k表达,首先默认最小数据a(k)为第一个数据，然后余下的4个数据分别跟a(k)比较，如果有比a(k)小的话，k重新赋值为最小数据的下标)
如果找到的最小数据下标k不是1(i)的话，那么与第一个数据元素发生交换(如果k<>i(i=1)，则a(k)与a(i)交换)
结果(第一个位置中的数据值最小，a(2)~a(5)为无序区域)i=1
k=1
for j=2 to 5
if a(j) k=j
next j
if k<>i then
t=a(k): a(k)=a(i):a(i)=t
End if第一遍排序选择排序的实现过程a(1)a(2)a(3)a(4)a(5)i=2用变量i表示第二遍处理，也表示第二个数据元素)
在第2至第5个数组元素中找最小数据 (最小数据的下标用变量k表达,首先默认最小数据a(k)为第二个数据，然后余下的3个数据分别跟a(k)比较，如果有比a(k)小的话，k重新赋值为最小数据的下标)
如果找到的最小数据下标k不是2(i)的话，那么与第二个数据元素发生交换(如果k<>i(i=2)，则a(k)与a(i)交换)
结果(第一个位置中的数据值最小，a(3)~a(5)为无序区域)i=2
k=2
for j=3 to 5
if a(j) k=j
next j
if k<>i then
t=a(k): a(k)=a(i):a(i)=t
End if第二遍排序选择排序的实现过程a(1)a(2)a(3)a(4)a(5)i=3用变量i表示第三遍处理，也表示第三个数据元素)
在第3至第5个数组元素中找最小数据 (最小数据的下标用变量k表达,首先默认最小数据a(k)为第三个数据，然后余下的2个数据分别跟a(k)比较，如果有比a(k)小的话，k重新赋值为最小数据的下标)
如果找到的最小数据下标k不是3(i)的话，那么与第三个数据元素发生交换(如果k<>i(i=3)，则a(k)与a(i)交换)
结果(第一个位置中的数据值最小，a(4)~a(5)为无序区域)i=3
k=3
for j=4 to 5
if a(j) k=j
next j
if k<>i then
t=a(k)
a(k)=a(i)
a(i)=t
End if第三遍排序选择排序的实现过程a(1)a(2)a(3)a(4)a(5)i=4用变量i表示第四遍处理，也表示第四个数据元素)
在第4至第5个数组元素中找最小数据 (最小数据的下标用变量k表达,首先默认最小数据a(k)为第四个数据，然后余下的1个数据分别跟a(k)比较，如果有比a(k)小的话，k重新赋值为最小数据的下标)
如果找到的最小数据下标k不是4(i)的话，那么与第四个数据元素发生交换(如果k<>i(i=4)，则a(k)与a(i)交换)
结果(第一个位置中的数据值最小，a(5)~a(5)为无序区域)i=4
k=4
for j=5 to 5
if a(j) k=j
next j
if k<>i then
t=a(k)
a(k)=a(i)
a(i)=t
End if第四遍排序5个数据进行选择排序的程序代码For i=1 to 4
k=i
for j=i+1 to 5
if a(j) next j
if k<>i then
t=a(k):a(k)=a(i):a(i)=t
End if
Next i对数组d中的n个数进行升序排序，其程序代码如下：For i=1 to n-1
k=i
for j=i+1 to n
if a(j) next j
if k<>i then
t=a(k):a(k)=a(i):a(i)=t
End if
Next i对数组d中的n个数进行降序排序，其方框处程序代码如何修改思考：在i到n中定位最小数的位置如果k<>i，则a(k)与a(i)交换课 堂 练 习1、某数组10个元素，依次为2、20、12、15、13、50、55、60、80、30，若采用选择排序算法进行降序排序，则第4遍排序完成时的数据序列为 （ ）B. 80、60、55、50、13、15、12、20、2、30A. 80、60、55、50、12、13、15、20、2、30C. 80、60、55、50、13、15、20、12、2、30D. 80、60、55、50、30、20、15、13、12、2B2、有6个数据，经过选择排序第一遍交换后，顺序为：21、65、36、84、45、72，则原始数据顺序不可能是（ ）A. 36、65、21、84、45、72 B. 84、65、36、21、45、72 C. 65、36、21、84、45、72 D. 45、65、36、84、21、72 C3、用选择排序法对数据7、6、3、9、2五个数据从大到小排序，共需经过（ ）次数据对调。 A. 10 B. 4 C. 5 D. 3D选择排序算法的流程图如图所示，请完成该算法的程序代码（以升序为例）Dim i, j, k, t As Integer
For i=1 To n-1
___________
For ___________
If d(j) ______________
End if
Next j
If k<>i Then
__________________________
End if
Next ik=ij = i+1 to nk= j t=a(k):a(k)=a(i):a(i)=t练习题1、某校通过政府投标中心采购一套多媒体教学设备，有5家单位参加竞标，竞标价分别为19万、15万、21万、13万、12万元人民币。若采用选择排序算法对标价从大到小排序，需要进行数据互换的次数是 （ ）A. 1 B. 2 C. 3 D. 4B2．某食品连锁店5位顾客贵宾消费卡的积分依次为900、512、613、700、810，若采用选择排序算法对其进行从小到大排序，如下表，第二趟的排序结果是（??? ）?????????????????? A．512?? ?613?? ?700? ??900?? ?810?? ?B．512? ??810? ??613? ??900? ??700?
?C．512?? ?900? ??613?? ?700?? ?810 ?D．512? ??613?? ?900?? ?700?? ?810D3、有6位裁判为运动员评分，给出的分数分别为49、45、61、46、58、57。采用选择排序对其进行排序，若完成第一遍时的结果为：61、45、49、46、58、57，则完成第二遍时的结果是（ ）
61、45、49、46、58、57 B. 61、58、57、49、45、46
C. 61、58、57、46、45、49 D. 61、58、49、46、45、57D4、用选择排序算法对一组学生的身高数据进行升序排序，已知第一遍排序结束后的数据序列为165、168、178、175、171，则下列选项中可能是原始数据序列的是： （ ）
175、178、168、165、171 B. 178、168、165、175、171
C. 165、178、168、175、171 C.165、168、171、175、178B5、有如下程序段：s=“ “
For i=1 to 3
h=1
For j=i+1 To 8
If a(h) Next j
If i<>h Then
t=a(i) : a(i)=a(h) : a(h)=t
End If
s=s+Str(h)
Next i
Text1.Text=s数组元素a(1)到a(8)的数据依次为“2，5，20，9，10，8，11，1”经过该程序段“加工”后，文本框Text1中显示的内容是（ ）8 1 2 B. 8 2 1
C. 3 7 5 D. 3 5 7C6、对数组元素a(1)到a(8)进行升序排序，其排序算法的VB部分程序段如下：For m=1 To 7
p=m
For n=m+1 To 8
Next n
If p<>m Then
t=a(p) : a(p)=a(m) : a(m)=t
Next m方框中的语句是（ ）A. If a(n)C. If a(n)>a(p) Then p=n D. If a(n)>a(p) Then p=mB7、下列VB程序段是选择排序程序的主要部分。其中虚线框内代码用于寻找数据元素d(i)到d(n)的最小值。……
For i=1 To n-1k=I
For j=i+1 To n
If d(j)Next j If i<>k Then t=d(i) : d(i)=d(k) : d(k)=t
Next i
……框内代码运行结速时，保存最小值的数组元素一定是（ ）A. d(n) B. d(j) C. d(i) D. d(k)D8、10位选手参加面试的顺序通过抽签决定。小陈设计了一个抽签排序的VB程序，功能如下：该程序远行时，在左边列表框List1中显示所有选手的编号与抽签号，单击“排序”按钮Command1，选手的信息按抽签号从小到大排序，并将结果显示在右边列表框List2中。实现该功能的VB程序如下，但加框处代码有错，请改正。Dim a(1 to 10) As String 数组a用于储存10位选手编号
Dim b(1 to 10) As Integer 数组b用于储存10位选手的抽签号
Form_Load 过程用于数组a和数组b的赋值，并显示在列表框List1中
Private Sub Form_Load
第i位选手编号存储在a(i)中，该选手的抽签号储存在b(i)
代码略
End Sub
Private Sub Command Click( )
Dim k As Integer, i As Integer, j As Integer
Dim t1 As String, t2 As Integer
For i= 1 To 9
k=i
For j=i+1 To 1
If b(j) Next j
If k<>I Then
t1=a(i) : a(i)=a(k) : a(k)=t1
t2=b(i) : b(i)=b(k) : b(k)= t1
End if
Next i
For i=1 To 10
List1 . AddiItem Str(b(i)+” “+a(i)
Next I
End Sub（1）（2）（3）（1）处应该为：________（2）处应该为：________（3）处应该为：________10t2List29、第K大的数。给定n（n<=128）个数和K的值，求出n个数中的第K大的数。假定：给定的n个数互不相同，且n大于等于K。
VB应用程序的运行界面如图所示：程序说明：由随机函数Rnd生成n个数（1—100之间）存放至数组d中，并显示在列表框List1中，n通过文本框Text1输入得到，K的值由文本框Text2得到。单击“查找”按钮，在Text3中显示统计结果。“查找”按钮的鼠标单击事件处理过程代码如下。将在程序中画线处的代码补充完整。
Private Sub Command1_Click()
Dim d(1 To 128) As Integer
Dim n As Integer, i As Integer, j As Integer, k As Integer
Randomize
n = Val(Text1.Text)
k = Val(Text2.Text)
List1.Clear
For i = 1 To n
d(i) = Int(100 * Rnd + 1)
List1.AddItem Str(d(i))
Next i For i = 1 To n - 1
p = i
For j = i + 1 To n
If d(p) < d(j) Then p = j
Next j
If p <> i Then
temp = d(i): d(i) = d(p): d(p) = temp
End If
Next i
List2.Clear
For i = 1 To n
List2.AddItem Str(d(i))
Next i
Text3.Text = Str(d(k))
End Sub