算法實例選擇排序法

1、小越中學(xué)信息技術(shù)組算法實例 選擇排序法1選擇排序算法的概念選擇排序算法是對冒泡排序算法的改進。這種方法是對參加排序數(shù)組的所有元素中找出最小(或最大)數(shù)據(jù)的元素，使它與第一個元素中數(shù)據(jù)相互交換位置。然后在余下的元素中找出最小(或最大)的數(shù)據(jù)的元素，與第二個元素中的數(shù)據(jù)交換位置。以此類推，直到所有元素成為一個有序的序列。某數(shù)組d共有4個元素構(gòu)成，每個元素的值如下表所示：數(shù)組元素數(shù)組元素d(1)d(2)d(3)d(4)值值1051239772用選擇排序法按升序進行排序的過程，從數(shù)組第一個元素開始起：第1遍：尋找從d(1)到d(4)范圍內(nèi)的最小數(shù)據(jù)d(k)，即k4，將d(1)與d(k)互換數(shù)據(jù)：共比較

2、數(shù)據(jù)3次，交換數(shù)據(jù)1次。第2遍：尋找從d(2)到d(4)范圍內(nèi)的最小數(shù)據(jù)d(k)，即k3，將d(2)與d(k)互換數(shù)據(jù)：共比較數(shù)據(jù)2次，交換數(shù)據(jù)1次。第3遍：尋找從d(3)到d(4)范圍內(nèi)的最小數(shù)據(jù)d(k)，即k4，將d(3)與d(k)互換數(shù)據(jù)：總共比較數(shù)據(jù)1次，交換數(shù)據(jù)1次。顯然，通過上述3遍處理，數(shù)組d中最小、第2小、第3小的數(shù)據(jù)已經(jīng)分別存儲在數(shù)組元素d(1)、d(2)、d(3)中，即數(shù)組元素d(1)到d(3)變?yōu)橛行?，而剩下的d(4)中的數(shù)據(jù)自然是數(shù)組中的最大數(shù)據(jù)。因此，通過3遍這樣的處理，整個數(shù)組內(nèi)的數(shù)據(jù)將是有序的。4個元素共需進行3遍加工處理，總的比較次數(shù)為3216次，而總計交換次數(shù)

3、每一遍一次，共計只有3次。對于n個元素的數(shù)組，用選擇算法進行排序時，比較次數(shù)與冒泡算法相同，但交換的次數(shù)比冒泡排序要少，因此它具有較高的效率。因此它具有較高的效率。2選擇排序算法的程序?qū)崿F(xiàn)選擇排序的程序同樣采用雙重For循環(huán)嵌套來實現(xiàn)，外循環(huán)來控制是第幾遍加工，內(nèi)循環(huán)用來控制數(shù)組內(nèi)進行排序元素的下標(biāo)變化范圍。在每一遍加工結(jié)束，都需要用一個變量來存儲這一遍加工中所找出的最小(或最大)的數(shù)據(jù)在數(shù)組內(nèi)的下標(biāo)。現(xiàn)有n個數(shù)據(jù)，分別存放在數(shù)組變量a(1 To n)當(dāng)中，采用選擇排序算法程序?qū)崿F(xiàn)其從小到大的程序結(jié)構(gòu)如下：實現(xiàn)該算法的程序段如下：For i1 To n1kiFor ji1 to n If a(

4、j)a(k) Then kjNext jIf ik Thenta(i)：a(i)a(k)：a(k)tEnd IfNext i當(dāng)外循環(huán)變量i取1時，為第1遍加工，k1，先假設(shè)第1個數(shù)據(jù)元素為最小值，內(nèi)循環(huán)從第2個數(shù)開始比較，如果a(2)小于a(1)，則將a(2)的下標(biāo)賦值給k，否則k值不變，這個方法目的是保證k是本遍加工最小數(shù)據(jù)元素的下標(biāo)。這樣，內(nèi)循環(huán)一次完成之后，判斷k是不是a(1)的下標(biāo)1，如果不是，則把a(k)與a(1)的數(shù)據(jù)進行交換，否則就不進行交換。這樣，第1遍加工后，就能把最小的數(shù)據(jù)存放在a(1)中。當(dāng)外層循環(huán)變量i取2時，為第2遍加工，找出a(2)到a(n)之間的最小數(shù)，記錄好它的

5、下標(biāo)k，把最小的數(shù)據(jù)放到a(2)中。這樣，每遍加工，都能找出最小數(shù)的下標(biāo)k，比較是不是i，如果不是，就將a(k)與a(i)交換。經(jīng)過n1遍之后，就能實現(xiàn)從小到大的排序。選擇排序的關(guān)鍵在于最小值變量k的值在不斷的發(fā)生變化，而每一遍加工，最多只交換一次數(shù)據(jù)，所以排序的效率比冒泡排序要高。本節(jié)的學(xué)習(xí)要求掌握選擇排序的基本思想，能根據(jù)選擇排序的思想來進行選擇排序的操作。掌握用程序來實現(xiàn)選擇排序的算法，能根據(jù)生活中的實際要求編寫選排排序的程序，從而進一步熟悉多重循環(huán)程序的編寫?？疾榉绞綖檫x擇題與填空題。1. 用選擇排序算法對一組學(xué)生的身高數(shù)據(jù)進行升序排序，已知第一遍排序結(jié)束后的數(shù)據(jù)序列為166、169、

6、177、175、172，則下列選項中可能是原始數(shù)據(jù)序列的是 ()A175、177、169、166、172 B177、169、166、175、172C166、177、169、175、172 D166、169、172、175、177B 2有6位裁判為運動員評分，給出的分數(shù)分別為48、45、63、46、59、57。采用選擇排序算法對其進行排序，若完成第一遍時的結(jié)果為：63、45、48、46、59、57，則完成第二遍時的結(jié)果是 ()A63、45、48、46、59、57 B63、59、57、48、45、46C63、59、57、46、45、48 D63、59、48、46、45、57 D3某校通過政府招投標(biāo)

7、中心采購一套多媒體教學(xué)設(shè)備，有5家單位參加競標(biāo)，競標(biāo)價分別為18萬、17萬、23萬、15萬、16萬元人民幣。若采用選擇排序算法對標(biāo)價從大到小排序，需要進行數(shù)據(jù)互換的次數(shù)是 ()A1 B3C4 D5B 4圣誕節(jié)即將來臨，某商場欲對倉庫某貨號商品進行補倉以應(yīng)對即將舉辦的促銷活動。6家供貨商給出的報價分別為48、43、60、46、58、55，若采用選擇排序算法對其進行從大到小排序，則第三遍的排序結(jié)果是()C 原始數(shù)據(jù)原始數(shù)據(jù)484360465855第第1遍遍604348465855第第2遍遍605848464355第第3遍遍第第4遍遍605855484346第第5遍遍605855484643A.60

8、、58、48、46、43、55 B.60、43、48、46、58、55C.60、58、55、46、43、48 D.60、58、55、48、46、435. 已知算法1與算法2都是排序算法，可能是冒泡排序或者選擇排序，下面的表格反應(yīng)的是在不同量的數(shù)據(jù)下，排序時進行數(shù)據(jù)交換的次數(shù)，分析算法1與算法2最有可能的排序算法分別是 ()C 排序的數(shù)據(jù)個數(shù)排序的數(shù)據(jù)個數(shù)算法算法1的交換次數(shù)的交換次數(shù)算法算法2的交換次數(shù)的交換次數(shù)57311418228313537485284182171105291094A.冒泡排序冒泡排序 B選擇排序選擇排序C冒泡排序選擇排序 D選擇排序冒泡排序6. 下列關(guān)于排序的說法，錯誤

9、的是 ()A相對而言，選擇排序算法的效率比冒泡排序算法高B冒泡排序算法和選擇排序算法的都需要用到雙循環(huán)結(jié)構(gòu)C對于n個無序數(shù)據(jù)，不管是冒泡排序還是選擇排序，都要經(jīng)過n1遍加工D冒泡排序算法的程序?qū)崿F(xiàn)一般要用到數(shù)組變量k，而選擇排序則不需要C 7. 小明編寫了一個統(tǒng)計數(shù)組元素a(l)到a(n)中的“升序段”個數(shù)s(如圖所示的數(shù)據(jù)序列，其 “升序段”的個數(shù)等于3)的VB程序。部分程序代碼如下：k 0 s 0For i 2 To n If a(i) a(i 1) Then Else k 0 End If If k 1 Then s s 1 Next iTextl.Text Str(s) 方框中的正確語

10、句是()Akk1BK1CK1DKk1D 上虞區(qū)小越中學(xué)信息技術(shù)組1.利用已學(xué)的選擇排序算法，對初始數(shù)據(jù) 49,38,65,97,76,13,27,49，進行認真的排序，并詳細記錄分次加工過程，請列出每次加工的數(shù)據(jù)序列。序后 13 38 65 97 76 49 27 49第二趟排序后 13 27 65 97 76 49 38 49第三趟排序后 13 27 38 97 76 49 65 49第四趟排序后 13 27 38 49 76 97 65 49第五趟排序后 13 27 38 49 49 97 65 76第六趟排序后 13 27 38 49 49 65 97 76第七趟排序后 13 27 38

11、 49 49 65 76 97最后排序結(jié)果 13 27 38 49 49 65 76 972.請完善選擇排序算法的通用流程圖(從小到大的順序)。 【例1】在2015年秋季學(xué)校運動會上，男生第一組6位選手的110米欄成績(單位：秒)分別是“18.4、17.3、16.9、18.8、18.1、16.7”，若使用選擇排序法將該組的成績按第一名、第二名、第三名的順序排序，則第一次交換數(shù)據(jù)后的順序是 () A.18.818.417.316.918.116.7 B.16.717.316.918.818.118.4 C.18.817.316.918.418.116.7 D.16.718.417.316.918

12、.818.1【例2】(浙江省2012年9月高考)實現(xiàn)某排序算法的部分VB程序如下： For i = 1 To 6k = iFor j = i + 1 To 7If a(j) a(k) Then k = jNext jIf i k Thent = a(i): a(i) = a(k): a(k) = tEnd IfNext i 在排序過程中，經(jīng)過某一遍排序“加工”后，數(shù)組元素a(1)到a(7)的數(shù)據(jù)依次為“10，41，75，12，63，11，85”。則下一遍排序“加工”后數(shù)組元素a(1)到a(7)的數(shù)據(jù)依次是（） A. 10, 11, 41, 75, 12, 63, 85 B. 10, 11, 7

13、5, 12, 63, 41, 85 C. 10, 11, 12, 75, 63, 41, 85 D. 10, 11, 12, 41, 63, 75, 85上虞區(qū)小越中學(xué)信息技術(shù)組1.選擇排序的基本思想是在所有的記錄中選出最小(大)的數(shù)據(jù)，把它與第一個數(shù)據(jù)交換，然后在其余的記錄中再選出最小(大)的數(shù)據(jù)與第二個數(shù)據(jù)交換，依此類推，直至所有數(shù)據(jù)排序完成。有一組數(shù)據(jù)，順序是“4、6、2、8、9”，用選擇排序法將這組數(shù)據(jù)從大到小排序，第二遍交換數(shù)據(jù)后的順序是 （） A.9、4、6、2、8 B.9、8、4、2、6 C.9、8、2、4、6 D.9、8、2、6、4練習(xí)2.電視臺為了統(tǒng)計參賽選手的短信支持度，來

14、確定參賽選手的人氣，對觀眾短信進行記錄，針對這一情況編寫程序過程中效率最高的算法是 （） A.枚舉算法B.解析算法C.選擇排序D.冒泡排序3.有一組原始數(shù)據(jù)：21.0、35.3、31.6、12.8、37.0、19.0，利用選擇排序算法進行從小到大的排序，經(jīng)過第二次加工后的數(shù)據(jù)排列順序是 （） A.19.0、21.0、35.3、31.6、12.8、37.0 B.19.0、35.3、31.6、12.8、37.0、21.0C.12.8、35.3、31.6、21.0、37.0、19.0 D.12.8、19.0、31.6、21.0、37.0、35.3上虞區(qū)小越中學(xué)信息技術(shù)組 4.有一組原始數(shù)據(jù)： gam

15、e、car、oae、eat、win、base、dog，利用選擇排序算法進行從小到大的排序， 經(jīng)過第二次加工后的數(shù)據(jù)排列順序是 （） A.base、car、game、oae、eat、win、dog B.base、game、car、oae、eat、win、dog C.base、car、oae、eat、win、game、dog D.base、dog、game、car、oae、eat、win算法應(yīng)用開發(fā)工程師職業(yè)概述：如果要問程序設(shè)計的靈魂是什么，相信很多人都會回答是算法，一個優(yōu)秀的算法工程師往往可以帶來生產(chǎn)力的巨大提升。當(dāng)你為實現(xiàn)某一功能而冥思苦想、費盡周折時，可能你需要的只是另一個精辟而又簡潔的算法。工作內(nèi)容：設(shè)計和優(yōu)化應(yīng)用算法，并協(xié)助完成應(yīng)用軟件方案設(shè)計及算法設(shè)計；獨立完成數(shù)學(xué)建模及算法設(shè)計；編寫相關(guān)技術(shù)文檔。職業(yè)要求：教育培訓(xùn)： 應(yīng)用數(shù)學(xué)、計算機等相關(guān)專業(yè)本科以上學(xué)歷。工作經(jīng)驗：算法開發(fā)人員重在很強的邏輯思維能力。并且需要熟練掌握數(shù)學(xué)建模、應(yīng)用算法的設(shè)計和優(yōu)化理論；精通C/C+ 或其他一種編程語言；熟悉數(shù)據(jù)庫的接口技術(shù)。薪資行情：一般月薪范圍45001