算法與程序設(shè)計(jì)——選擇排序
[小組討論]選擇排序的實(shí)質(zhì)是每次把一堆數(shù)據(jù)中的最小數(shù)移到某個(gè)位置，那么這樣的操作在規(guī)模為n的數(shù)組中會(huì)做多少次？
——n-1次，因?yàn)榻?jīng)過(guò)n-1次操作已經(jīng)確定了第1到n-1個(gè)位置的次序，第n個(gè)位置也自然可以確定。
[小組討論]找出數(shù)組中的最小數(shù)用什么策略?
[復(fù)習(xí)鞏固]可以借助一個(gè)自定義的integer型變量min，用它記錄最小的一個(gè)數(shù)據(jù)的下標(biāo)。
首先，不管實(shí)際情況如何，我們先假設(shè)數(shù)組中第1個(gè)元素為最小，于是有min=1，再把這個(gè)元素與從第2個(gè)元素開(kāi)始的所有元素作比較，一旦有比d(min)更小的元素存在，則修改min變量值為新的較小元素下標(biāo)。這樣，在d(min)經(jīng)過(guò)了從第2個(gè)元素到最后一個(gè)元素的一一比較后，所得到min應(yīng)該就是第1到n個(gè)元素中的選舉出來(lái)的最小元素下標(biāo)了。
然后用類似的方法，把第2到n個(gè)元素中最小數(shù)選舉出來(lái)；把第3到n個(gè)元素中最小數(shù)選舉出來(lái)……
i←1:min←1:j←2
開(kāi)始
j<n ?
d(j)<d(min) ?
min←j
y
y
n
………………
j=j+1
最后把每次選舉出來(lái)的結(jié)果依次輸出即可實(shí)現(xiàn)升序排列。
[學(xué)生完成第1遍處理過(guò)程的流程圖片斷]
[依據(jù)流程圖寫出代碼]
dim min as integer
dim j as integer
min=1
for j=2 to n
if d(j)<d(min) then min=j
next j
[小組討論]
在遍歷了一遍后如果發(fā)現(xiàn)第1-n個(gè)數(shù)中的最小數(shù)d(min)，根據(jù)選擇排序的思想，需要把它與第1個(gè)數(shù)字進(jìn)行交換。如何進(jìn)行？
[請(qǐng)同學(xué)發(fā)言]打個(gè)比方，在廚房里有一瓶醬油、一瓶醋和一個(gè)空瓶，如何利用這個(gè)空瓶實(shí)現(xiàn)醬油與醋？
——可先把醬油倒到空瓶中，再把醋倒到原來(lái)裝醬油的瓶中，然后從原來(lái)的空瓶中把醬油倒到原來(lái)裝醋現(xiàn)在已經(jīng)空的瓶中，即可實(shí)現(xiàn)換位。
[教師]大家動(dòng)動(dòng)腦筋，用這種思想，試試把d(1)與d(min)換位，并寫出相應(yīng)的代碼。
dim temp as integer
temp = d(i):d(i)=d(min):d(min)=temp ’關(guān)鍵在于引入“空瓶”變量temp
[思考]是不是每遍歷一遍后必須做這樣的一次交換？
——不是必須的，只有當(dāng)確實(shí)發(fā)現(xiàn)有比d(1)小的數(shù)后才交換
[教師]那怎么知道有沒(méi)有發(fā)現(xiàn)比d(1)更小的數(shù)呢？
i←1:min←1:j←2
開(kāi)始
j<n ?
d(j)<d(min) ?
min←j
y
n
n
………………
min<>1 ?
temp = d(1)
d(1)=d(min)
d(min)=temp
y
j=j+1
——其實(shí)在遍歷之前我們已經(jīng)假設(shè)第1個(gè)元素最小，即min=1，所以在遍歷一遍后我們只需要驗(yàn)證一下min=1是否還成立。成立則表明沒(méi)有比第1個(gè)元素小的數(shù)，不成立則表明有比第1個(gè)元素小的數(shù)，且它的下標(biāo)為min，此時(shí)要交換d(1)與d(min)。
[學(xué)生完善流程圖及代碼]
if min <> 1 then
temp = d(1):d(1)=d(min):d(min)=temp
end if
[教師]我們先前說(shuō)過(guò)，對(duì)于規(guī)模為n的數(shù)組，需要遍歷處理次數(shù)為n-1次，以上的流程就是這n-1次中需要重復(fù)做的事，對(duì)于重復(fù)處理的事，可以用什么結(jié)構(gòu)？
——循環(huán)，以上的比較、交換即為循環(huán)體
[教師]大家試著把這個(gè)循環(huán)結(jié)構(gòu)流程圖畫出來(lái)
[學(xué)生完善流程圖及代碼]
開(kāi)始
j<n ?
d(j)<d(min) ?
min←j
y
n
輸出排序結(jié)果
n
min<>i ?
temp = d(i)
d(i)=d(min)
d(min)=temp
y
i<=n-1
i←1
y
n
結(jié)束
i=i+1
j=j+1
min=i:j=i+1
for i = 1 to n-1
min = i
for j = i + 1 to n