資源簡介

第3節　選擇排序及程序實現
考試內容
考試要求
選擇排序算法思想
c
選擇排序程序實現
c
一、選擇排序算法思想
每趟排序是在所有的數據中找出最大(或最小)的數據，與第一個數據交換位置，然后再在剩下的數據中找出最大(或最小)的數據，與第二個數據交換位置，以此類推，直到所有元素成為一個有序序列為止。
n個數據排序共需進行n－1趟(遍)排序。
二、選擇排序算法框架
設定：對數組d中的n個數據進行升序排序。
(1)從前往后進行比較
For i ＝ 1 To n － 1　′n個排序共進行n－1趟排序
　假定i位置上的數為最小數
　For j ＝ i ＋ 1 To n　′i后面的位置
　′若找到更小的數，則將用k記錄此數的位置
　Next j
　If k < > i Then　′若i位置上的數不是最小數，則和k位置上的數進行互換
交換d(i)與d(k)
　End If
Next i
注：若要按降序排列，將程序中的語句“If d(k)>d(j)”改為“If d(k)(2)從后往前進行比較
For i ＝ 1 To n － 1　′n個排序共進行n－1趟排序
　假定i位置上的數為最小數
　For j ＝ n To i ＋ 1　Step －1　 ′i后面的位置
　′若找到更小的數，則將用k記錄此數的位置
　Next j
　If k < > i Then　′若i位置上的數不是最小數，則和k位置上的數進行互換
　交換d(i)與d(k)
　End If
Next i
注：若要按降序排列，將程序中的語句“If d(k)>d(j)”改為“If d(k)三、選擇排序程序實現
設定：對數組d中的n個數據進行升序排序。
(1)從前往后進行比較
For i ＝ 1 To n － 1　′n個排序共進行n－1趟排序
　k ＝ i　　　　　　′假定i位置上的數為最小數
　For j ＝ i ＋ 1 To n　　　 ′i后面的位置
　 If d(k) > d(j) Then k ＝ j　′若找到更小的數，則將用k記錄此數的位置
　Next j
　If k < > i Then　′若i位置上的數不是最小數，則和k位置上的數進行互換
temp＝d(k)：d(k)＝d(i)：d(i)＝temp
　End If
Next i
(2)從后往前進行比較
For i ＝ 1 To n － 1　′n個排序共進行n－1趟排序
　k ＝ i　′假定i位置上的數為最小數
　For j ＝ n To i ＋ 1 Step －1　′i后面的位置
If d(k) > d(j) Then k ＝ j　′若找到更小的數，則將用k記錄此數的位置
　Next j
　If k < > i Then　′若i位置上的數不是最小數，則和k位置上的數進行互換
temp＝d(k)：d(k)＝d(i)：d(i)＝temp
　End If
Next i

一、選擇排序算法思想
理解選擇排序的基本思想，學會將待排數據按照選擇算法思想進行手工模擬排序。
【典例1】 使用選擇排序對下表中9個數據進行排序，排序過程如下所示：
初始數據
100
50
80
70
60
35
90
85
25
第1遍
100
50
80
70
60
35
90
85
25
第2遍
100
90
80
70
60
35
50
85
25
第3遍
則第三遍的排序結果為(　　)
A.100，90，85，80，70，60，35，50，25
B.100，90，85，70，60，35，50，80，25
C.100，90，85，80，70，60，50，35，25
D.100，90，85，60，70，35，50，80，25
解析　本題主要考查選擇排序算法的基本思想。觀察第1、2遍的排序結果可知，該選擇排序為降序排序，第3遍排序時，數據85與80進行交換，因此第三遍排序后的結果為“100，90，85，70，60，35，50，80，25”，答案為B。
答案　B
【變式訓練】 采用選擇排序算法對數組d中的8個數據“20，8，6，4，15，3，19，50”進行排序，部分程序如下：
For i＝1 To 5
k ＝ i
For j＝i＋1 To 8
If d(j)If i< >k Then
tt＝d(k)：d(k)＝d(i)：d(i)＝tt
End If
　Next j
Next i
該程序段執行后，數組元素d(1)～d(8)依次為(　　)
A.3，4，6，8，15，19，20，50
B.3，4，6，8，15，50，20，19
C.3，4，6，8，15，20，19，50
D.3，4，6，8，15，20，50，19
解析　本題主要考查的是選擇排序。根據語句“If d(j)初始數據
20
8
6
4
15
3
19
50
第1遍
3
8
6
4
15
20
19
50
第2遍
3
4
6
8
15
20
19
50
第3遍
3
4
6
8
15
20
19
50
第4遍
3
4
6
8
15
20
19
50
第5遍
3
4
6
8
15
20
19
50
因此答案為C。
答案　C
【方法總結】 選擇排序時，首先用變量記錄最大或最小元素的位置，然后與相應位置上的元素進行交換；通過If語句中表達式確定排序的升降性。
二、選擇排序算法實例應用
【典例2】 有如下VB程序段：
For n ＝ 1 To 4
　p ＝ n
　For m ＝ n ＋ 1 To 5
If a(m) < a(p) Then p ＝ m
　Next m
　If p > n Then
temp ＝ a(n)
a(n) ＝ a(p)
a(p) ＝ temp
　End If
Next n
設數組元素a(1)～a(5)的值分別為“1000，1200，1018，1208，1019”，經過該程序段“加工”后，數組元素a(1)＋a(3)的值為(　　)
A.2018 B.2019
C.2200 D.2208
解析　本題主要考查的是選擇排序算法。排序方式為升序，排序后數組元素a(1)～a(5)的值分別為“1000，1018，1019，1200，1208”，因此a(1)＋a(3)＝1000＋1019＝2019。
答案　 B
【變式訓練】 小趙對選擇排序算法進行了如下改進：在數組的所有元素中找出最小和最大數據的元素，然后將這兩個元素分別與第一個和最后一個元素交換數據，在余下的元素中找出最小和最大數據的元素，分別與第二個和倒數第二個元素交換數據，以此類推，直到所有元素的數據按升序排列。小趙編寫的VB程序段如下：
p ＝ 1: q ＝ 10
Do While p < q
　iMin ＝ p: iMax ＝ p
　For i ＝ p ＋ 1 To q
If a(i) < a(iMin) Then iMin ＝ i
If a(i) > a(iMax) Then iMax ＝ i
　Next i
　t ＝ a(iMin): a(iMin) ＝ a(p): a(p) ＝ t
　____①____
　t ＝ a(iMax): a(iMax) ＝ a(q): a(q) ＝ t
　p ＝ p ＋ 1
　q ＝ q － 1
Loop
要使程序實現上述算法思想，則程序中劃線處的語句是(　　)
A.If iMax ＝ p Then iMax ＝ iMin
B.If iMin ＝ p Then iMin ＝ iMax
C.If iMax ＝ p Then iMin ＝ iMax
D.If iMin ＝ p Then iMax ＝ iMin
解析　本題考查的是選擇排序算法的變式。選擇排序的原本思想是找出一個最大(或最小)的元素將它與第一個元素進行互換，本題的選擇排序算法思想是：首先找出當前數據中的一個最小元素和一個最大元素，然后將最小元素與隊首元素交換，將最大元素與隊尾元素進行互換。當最大元素在p位置時，由于它與最小元素進行互換后，原來的存放位置發生了變化，即由p的位置更改為iMin的位置了，因此要將它的新位置記錄在iMax中，然后再與q位置上的元素進行互換。因此，答案為A。
答案　A
【方法總結】 在掌握選擇排序常規算法的基礎上，還要對選擇排序的各種變式進行研究，做到舉一反三，觸類旁通。
1.對數組元素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)B.If a(n)C.If a(n)>a(p) Then p＝n
D.If a(n)>a(p) Then p＝m
解析　本題主要考查的是選擇排序的程序實現。要降序排序，因此劃線處的語句為If a(n)答案　B
2.實現某排序算法的部分VB程序如下：
For i ＝ 1 To 7
　 k ＝ i
　 For j ＝ i ＋ 1 To 8
　 If a(j) < a(k) Then k ＝ j
　 Next j
　 If i < > k Then
　 t ＝ a(i): a(i) ＝ a(k): a(k) ＝ t　
　 End If
Next i
在排序過程中，經過某一遍排序“加工”后，數組元素a(1)到a(8)的數據依次為“1，2，15，8，16，7，6，5”。則下一遍排序“加工”后數組元素a(1)到a(7)的數據依次是(　　)
A.1，2，5，6，7，8，15，16
B.1，2，5，15，16，7，6，8
C.1，2，5，8，16，6，7，15
D.1，2，5，8，16，7，6，15
解析　本題主要考查的是選擇排序(升序)的實現過程。根據程序代碼或給出的數據序列可知，是升序排序，前2個數已經有序，因此下一遍的排序是剩下的6個元素中選出一個最小數與第三個位置上的元素進行交換，即15與5交換。
第i遍
1
2
15
8
16
7
6
5
第i＋1遍
1
2
5
8
16
7
6
15
具體排序如表。
答案　D
3.十佳歌手評選。某校舉行學生歌唱比賽，得分最高的前十名選手為校園十佳歌手。下面的Visual Basic程序用于解決這一問題，數組a中存儲了參賽學生的編號，數組b中存儲了參賽學生的得分，原始信息顯示在列表框List1中，單擊“計算”按鈕后，“得分”最高的10名學生的信息顯示在列表框List2中，程序運行界面如圖所示。
程序代碼如下：
Const n ＝ 80
Dim a(1 To n) As String, b(1 To n) As Single
Private Sub Command1_Click()
　 Dim i As Integer, j As Integer, m As Integer
　 Dim s As String, t As Single
For i ＝ 1 To n － 1
m ＝ i
For j ＝ i ＋ 1 To n
　 If ____①____ Then m ＝ j
Next j
If____②____ Then
　s ＝ a(i): a(i) ＝ a(m): a(m) ＝ s
　t ＝ b(i): b(i) ＝ b(m): b(m) ＝ t
End If
Next i
For i ＝ 1 To 10
List2.AddItem a(i) ＋ “　 ” ＋ Str(b(i))
　 Next i
End Sub
Private Sub Form_Load()
′此過程用于對數組a和數組b進行賦值，并顯示在List1中，代碼略
End Sub
(1)程序中加框部分的算法是________________(選填：選擇排序/冒泡排序)。
(2)在程序①和②劃線處，填入適當的語句或表達式，把程序補充完整。
解析　本題主要考查的是選擇排序算法。十佳歌手的評選是按照選手的得分降序排序，取前十名得到的，數組b存儲的是選手的得分，因此①處的語句為b(m)m。
答案　(1)選擇排序 (2)①b(m) < b(j)?、趇 < > m
基礎鞏固
1.有如下程序段：
For i ＝ 1 To 2
For j ＝ i ＋ 1 To 5
　If a(j) > a(i) Then t ＝ a(j): a(j) ＝ a(i): a(i) ＝ t
Next j
Next i
數組元素a(1)～a(5)的值依次為“3，11，19，17，7”，經過該程序段“加工”后，數組元素a(1)到a(5)的值依次為(　　)
A.3，7，11，17，19 B.19，17，11，7，3
C.19，17，3，11，7 D.19，17，3，7，11
解析　本題主要考查的是選擇排序算法。這是普通的選擇排序，每遍排序時將i位置的元素順序與它后面的元素比較，若比它大，則交換它們的位置。本程序是求二遍降序排序后數據的順序。
答案　C
2.有如下VB程序段：
For n ＝ 1 To 4
　p ＝ n
　For m ＝ n ＋ 1 To 5
If a(m) < a(p) Then p ＝ m
　Next m
　 If p > n Then
temp ＝ a(n)
a(n) ＝ a(p)
a(p) ＝ temp
　End If
Next n
設數組元素a(1)～a(5)的值分別為“1000，1200，1018，1208，1019”，經過該程序段“加工”后，數組元素a(1)＋a(3)的值為(　　)
A.2018 B.2019
C.2200 D.2208
解析　本題主要考查的是選擇排序算法。排序方式為升序，排序后數組元素a(1)～a(5)的值分別為“1000，1018，1019，1200，1208”，因此a(1)＋a(3)＝1000＋1019＝2019。
答案　 B
3.某排序算法的VB程序段如下：
　n ＝ 10
　For i ＝ n To 8 Step －1
p ＝ i
For j ＝ i － 1 To 1 Step －1
　 If a(p) > a(j) Then p ＝ j
Next j
If p < i Then
　 tt ＝ a(p): a(p) ＝ a(i): a(i) ＝ tt
End If
　Next i
　For i ＝ 1 To n
s ＝ s ＋ Str(a(i))
　Next i
　Text1.Text ＝ s
End Sub
數組元素a(1)到a(10)的值依次為“92，1，84，52，69，50，29，68，87，19”，執行該程序段，文本框Text1中顯示的是(　　)
A.92 87 84 69 68 52 50 29 19 1
B.92 87 84 52 69 50 68 29 19 1
C.92 87 84 69 52 50 68 29 19 1
D.92 87 84 52 50 69 68 29 19 1
解析　本題是選擇排序算法的一種變式。本題的選擇排序進行的方式為：從后往前進行排序，即從后往前找到一個最小數，然后讓其與最后一個數進行交換位置，再從后往前找到第二小的數，讓其與倒數第二個數交換位置，共進行3趟排序，求三趟排序后數列的情況。
答案　B
4.某程序運行界面如圖所示。程序運行時，單擊“生成隨機數”按鈕，將隨機生成n個[100，500]區間內的偶數，并在列表框List1中顯示；在文本框Text1中輸入整數k，單擊“排序”按鈕，將第k趟(遍)升序排序后的數據顯示在列表框List2中。
在程序中的劃線處，填入適當的語句或表達式，把程序補充完整.
Const n ＝ 12
Dim d(1 To n) As Integer
Private Sub Command1_Click()
　 Dim i As Integer
　 Randomize
　 For i ＝ 1 To n
　 d(i) ＝ Int(Rnd *____①____) * 2 ＋ 100
　 List1.AddItem Str(d(i))
　 Next i
End Sub
Private Sub Command2_Click()
　Dim k As Integer, i As Integer, j As Integer, t As Integer, p As Integer
　 k ＝ Val(Text1.Text)
　 For i ＝____②____
　 p ＝ i
　 For j ＝ i ＋ 1 To n
　　　 If ____③____ Then p ＝ j
　 Next j
　 If p < > i Then
　　　 t ＝ d(p): d(p) ＝ d(i): d(i) ＝ t
　 End If
　 Next i
　 For i ＝ 1 To n
　 List2.AddItem Str(d(i))
　 Next i
End Sub
解析?、俅a表示生成隨機數，隨機整數的范圍為[100，500]，括號內的范圍為[0，200]，因此，①處代碼為201；變量i表示排序的趟數，題目要求進行k趟排序，因此②處代碼為1 To k；排序方式為升序，因此③處代碼為d(p) > d(j)。
答案?、?01　②1 To k　③d(p) > d(j)
能力提升
5.有一組正整數，要求對其中的素數進行升序排序。排序后素數在前，非素數在后。排序示例如下。
Const n ＝ 8
Dim a(1 To n) As Integer
Private Sub Command1_Click()
　Dim i As Integer, j As Integer, k As Integer, t As Integer
　Dim flag As Boolean
　′讀取一組正整數，存儲在數組a中，代碼略
　For i ＝ 1 To n － 1
′(1)
If IsPrime(a(k)) Then flag ＝ True Else flag ＝ False
For j ＝ i ＋ 1 To n
　 If IsPrime(a(j)) Then
If  Then′(2)
　　　 k ＝ j
　　　 flag ＝ True
End If
　End If
Next j
If k < > i Then
　t ＝ a(k): a(k) ＝ a(i): a(i) ＝ t
End If
If Not flag Then Exit For　′Exit For表示退出循環
Next i
　′依次輸出排序后的數據。代碼略
End Sub
Function IsPrime(m As Integer) As Boolean
　′本函數判斷m是否是素數：是素數返回值為True，不是素數返回值為False
　′代碼略
End Function
程序中加框(1)處應改正為_________________________________________；
加框(2)處應改正為________________________________________________。
解析　本題主要考查的是選擇排序算法。本題對傳統的選擇排序進行變式，題意是對兩類數據進行選擇性排序。每趟排序進行時(升序)，首先將i位置上的元素當作是最小數，因此(1)處語句應改為k＝i，然后到它后面去找更小數，并將該數位置記錄在變量k中。變量flag表示每趟進行時i位置上的數是否為素數，如果當前i位置的數不是素數，則找到它后面的第一個素數作為基數，并用k記錄此素數的位置；如果素數已經出現過(flag＝True)，則該素數需要和它之前的素數比較大小，若當前素數更小，則更新k的值。
答案　(1)k＝i　(2)Not flag Or a(j) 6.小炫報名參加“智力大沖浪”節目。比賽規則如下：
比賽開始時參賽者將預先得到M元獎金。
比賽時間分為N個時段(N≤100)，有N個小游戲，每個時段可完成1個游戲，第i個小游戲必須在規定期限t(i)時段前完成(1≤t(i)≤N)，否則要從獎金M元中扣去獎金w(i)，w(i)為自然數，不同的游戲扣去的獎金是不一樣的。每個游戲必須從整時段開始。注意：比賽絕對不會讓參賽者賠錢！
例如：當N＝5，M＝100時
游戲編號
1
2
3
4
5
完成期限t(i)
1
4
2
3
2
扣除獎金數w(i)
5
4
10
8
7
在這種情況下，小炫依次完成編號為5、3、4、2、1的小游戲，獲得了最高獎金95元。
他的算法思想：讓扣款高的游戲盡量準時完成?？鄢莫劷鹪缴伲瑒t最后贏取的獎金越多。
(1)按扣款數值從大到小排序，在樣例中，排序后游戲編號依次為3、4、5、1、2；
(2)對于游戲i，在時間段1到t(i)完成，效果都是一樣的，所以盡量放置的時間段t(i)完成，若該時段已經被占用，則依次考查時間段t(i)－1, t(i)－2，……，1。在樣例中，
①考慮游戲3，放置在時間段2完成(注：t(3)＝2)；
②考慮游戲4，放置在時間段3完成(注：t(4)＝3)；
③考慮游戲5，時間段2已被游戲3占用，放置在時間段1完成(注：t(5)－1＝1)；
④考慮游戲1，時間段1已被游戲5占用，不能按時完成，記錄扣款；
⑤考慮游戲2，放置在時間段4完成(注：t(2)＝4)
小炫按如上算法編寫了一個VB程序，計算“智力大沖浪”游戲中玩家最多可贏取的獎金，將結果輸出到文本框Text1中。
VB程序代碼如下所示，請在劃線處填入合適代碼。
Dim n As Integer, m As Integer
Dim t(1 To 100) As Integer　′變量t(i) 表示第i個游戲的完成期限
Dim w(1 To 100) As Integer　 ′變量w(i) 表示第i個游戲未完成要扣除的獎金
Dim f(1 To 100) As Boolean　 ′變量f(i)表示第i個時段是否已經被占用
Private Sub Form_Load()
　′初始化游戲設置信息，時段數量n、初始獎金數m 、數組t、數組w
　′代碼略
End Sub
Sub swap(x As Integer, y As Integer) ′自定義過程，用Call語句來調用該過程
　Dim z As Integer
　z ＝ x: x ＝ y: y ＝ z
End Sub
Sub sort()　′自定義過程，可以用Call語句來調用該過程
　Dim x As Integer, i As Integer, j As Integer
　For i ＝ 1 To n － 1
For j ＝ i ＋ 1 To n
　 If w(i) < w(j) Then
Call swap( w(i), w(j) )　′調用自定義過程
　　 ____①____
　 End If
Next j
　Next i
End Sub
Private Sub Command1_Click()
Dim i As Integer, k As Integer, p As Integer
　Call sort　′調用自定義過程
　tot ＝ 0
　For i ＝ 1 To n
f(i) ＝ True
　Next i
　For i ＝ 1 To n ′對每個游戲從該游戲的規定期限開始往左找可用時間段
　′找到可用時間段則完成該游戲，否則放棄該游戲
p ＝ －1
k ＝ t(i)
Do While k > 0 And p ＝ －1
　If f(k) ＝ True Then
p ＝ k
f(k) ＝ False
　 Else
　 ____②____
　 End If
Loop
If p ＝ －1 Then tot ＝ tot ＋ w(i)
　Next i
　____③____
　Text1.Text＝Str(ans)
End Sub
解析　本題主要考查的是選擇排序的樸素(非優化的)算法及程序綜合應用能力。自定義過程sort()的功能是將數據按游戲扣除獎金數的降序排序，因此在滿足條件時，除了交換扣除獎金數的數據外(t(i)與t(j))，還需交換游戲完成期限的數據，即交換t(i)與t(j)的值，因此①處應填入的語句為Call swap(t(i)，t(j))，也可以寫作Call swap(t(j)，t(i))；②處表示f(k) ＝ False時的情況，即第k個時段已被用掉，按照游戲規則，將往左尋找一個空的時段，因此②處語句為k＝k－1；變量tot表示扣除的總獎金數，m表示游戲開始前的總的獎金數，因此游戲結束時所獲得的獎金數ans為m－tot，故③處應填入的語句為ans＝m－tot。
答案?、賑all swap(t(i)，t(j))或Call swap(t(j)，t(i))
②k＝k－1?、踑ns＝m－tot
課件19張PPT。第3節　選擇排序及程序實現一、選擇排序算法思想每趟排序是在所有的數據中找出最大(或最小)的數據，與第一個數據交換位置，然后再在剩下的數據中找出最大(或最小)的數據，與第二個數據交換位置，以此類推，直到所有元素成為一個有序序列為止。
n個數據排序共需進行n－1趟(遍)排序。二、選擇排序算法框架設定：對數組d中的n個數據進行升序排序。
(1)從前往后進行比較
For i ＝ 1 To n － 1　′n個排序共進行n－1趟排序
　假定i位置上的數為最小數
　For j ＝ i ＋ 1 To n　′i后面的位置
　′若找到更小的數，則將用k記錄此數的位置
　Next j
　If k < > i Then　′若i位置上的數不是最小數，則和k位置上的數進行互換
交換d(i)與d(k)
　End If
Next i注：若要按降序排列，將程序中的語句“If d(k)>d(j)”改為“If d(k)(2)從后往前進行比較
For i ＝ 1 To n － 1　′n個排序共進行n－1趟排序
　假定i位置上的數為最小數
　For j ＝ n To i ＋ 1　Step －1　 ′i后面的位置
　′若找到更小的數，則將用k記錄此數的位置
　Next j
　If k < > i Then　′若i位置上的數不是最小數，則和k位置上的數進行互換　交換d(i)與d(k)
　End If
Next i
注：若要按降序排列，將程序中的語句“If d(k)>d(j)”改為“If d(k)(1)從前往后進行比較
For i ＝ 1 To n － 1　′n個排序共進行n－1趟排序
　k ＝ i　　　　　　′假定i位置上的數為最小數
　For j ＝ i ＋ 1 To n　　　 ′i后面的位置
　 If d(k) > d(j) Then k ＝ j　′若找到更小的數，則將用k記錄此數的位置
　Next j
　If k < > i Then　′若i位置上的數不是最小數，則和k位置上的數進行互換
temp＝d(k)：d(k)＝d(i)：d(i)＝temp
　End If
Next i(2)從后往前進行比較
For i ＝ 1 To n － 1　′n個排序共進行n－1趟排序
　k ＝ i　′假定i位置上的數為最小數
　For j ＝ n To i ＋ 1 Step －1　′i后面的位置
If d(k) > d(j) Then k ＝ j　′若找到更小的數，則將用k記錄此數的位置
　Next j
　If k < > i Then　′若i位置上的數不是最小數，則和k位置上的數進行互換
temp＝d(k)：d(k)＝d(i)：d(i)＝temp
　End If
Next i一、選擇排序算法思想理解選擇排序的基本思想，學會將待排數據按照選擇算法思想進行手工模擬排序?！镜淅?】 使用選擇排序對下表中9個數據進行排序，排序過程如下所示：則第三遍的排序結果為(　　)
A.100，90，85，80，70，60，35，50，25
B.100，90，85，70，60，35，50，80，25
C.100，90，85，80，70，60，50，35，25
D.100，90，85，60，70，35，50，80，25解析　本題主要考查選擇排序算法的基本思想。觀察第1、2遍的排序結果可知，該選擇排序為降序排序，第3遍排序時，數據85與80進行交換，因此第三遍排序后的結果為“100，90，85，70，60，35，50，80，25”，答案為B。
答案　B【變式訓練】 采用選擇排序算法對數組d中的8個數據“20，8，6，4，15，3，19，50”進行排序，部分程序如下：For i＝1 To 5
k ＝ i
For j＝i＋1 To 8
If d(j) If i< >k Then
tt＝d(k)：d(k)＝d(i)：d(i)＝tt
End If
　Next j
Next i該程序段執行后，數組元素d(1)～d(8)依次為(　　)
A.3，4，6，8，15，19，20，50
B.3，4，6，8，15，50，20，19
C.3，4，6，8，15，20，19，50
D.3，4，6，8，15，20，50，19解析　本題主要考查的是選擇排序。根據語句“If d(j)【典例2】 有如下VB程序段：For n ＝ 1 To 4
　p ＝ n
　For m ＝ n ＋ 1 To 5
If a(m) < a(p) Then p ＝ m
　Next m
　If p > n Then
temp ＝ a(n)
a(n) ＝ a(p)
a(p) ＝ temp
　End If
Next n設數組元素a(1)～a(5)的值分別為“1000，1200，1018，1208，1019”，經過該程序段“加工”后，數組元素a(1)＋a(3)的值為(　　)
A.2018 B.2019
C.2200 D.2208
解析　本題主要考查的是選擇排序算法。排序方式為升序，排序后數組元素a(1)～a(5)的值分別為“1000，1018，1019，1200，1208”，因此a(1)＋a(3)＝1000＋1019＝2019。
答案　 B【變式訓練】 小趙對選擇排序算法進行了如下改進：在數組的所有元素中找出最小和最大數據的元素，然后將這兩個元素分別與第一個和最后一個元素交換數據，在余下的元素中找出最小和最大數據的元素，分別與第二個和倒數第二個元素交換數據，以此類推，直到所有元素的數據按升序排列。小趙編寫的VB程序段如下：p ＝ 1: q ＝ 10
Do While p < q
　iMin ＝ p: iMax ＝ p
　For i ＝ p ＋ 1 To q
If a(i) < a(iMin) Then iMin ＝ i
If a(i) > a(iMax) Then iMax ＝ i　Next i
　t ＝ a(iMin): a(iMin) ＝ a(p): a(p) ＝ t
　____①____
　t ＝ a(iMax): a(iMax) ＝ a(q): a(q) ＝ t
　p ＝ p ＋ 1
　q ＝ q － 1
Loop要使程序實現上述算法思想，則程序中劃線處的語句是(　　)
A.If iMax ＝ p Then iMax ＝ iMin
B.If iMin ＝ p Then iMin ＝ iMax
C.If iMax ＝ p Then iMin ＝ iMax
D.If iMin ＝ p Then iMax ＝ iMin解析　本題考查的是選擇排序算法的變式。選擇排序的原本思想是找出一個最大(或最小)的元素將它與第一個元素進行互換，本題的選擇排序算法思想是：首先找出當前數據中的一個最小元素和一個最大元素，然后將最小元素與隊首元素交換，將最大元素與隊尾元素進行互換。當最大元素在p位置時，由于它與最小元素進行互換后，原來的存放位置發生了變化，即由p的位置更改為iMin的位置了，因此要將它的新位置記錄在iMax中，然后再與q位置上的元素進行互換。因此，答案為A。答案　A【方法總結】 在掌握選擇排序常規算法的基礎上，還要對選擇排序的各種變式進行研究，做到舉一反三，觸類旁通。

展開更多......

收起↑