大學(xué)計(jì)算機(jī)基礎(chǔ) 課件 10.3.3直接插入排序

大學(xué)計(jì)算機(jī)基礎(chǔ)——基于計(jì)算思維（Windows10+Office2016）第10章算法思維與運(yùn)用10.3.3直接插入排序10.3排序算法1．問(wèn)題分析直接插入排序班級(jí)花名冊(cè)已按學(xué)號(hào)排好了，但突然轉(zhuǎn)來(lái)了其他幾位學(xué)生（已有學(xué)號(hào)，入學(xué)后就不會(huì)變）。軍訓(xùn)已有某些人按高低順序排好了隊(duì)，后來(lái)又來(lái)了一些人。怎樣將這幾位同學(xué)也按學(xué)號(hào)排到花名冊(cè)中呢?這些人怎樣插入到隊(duì)列中而不影響隊(duì)伍的高低順序呢？例如例如1．問(wèn)題分析直接插入排序?qū)τ谂R時(shí)產(chǎn)生的無(wú)序數(shù)據(jù)要實(shí)現(xiàn)實(shí)時(shí)排序采用直接插入排序1．問(wèn)題分析直接插入排序直接插入排序能實(shí)現(xiàn)實(shí)時(shí)排序，是因?yàn)槌藷o(wú)序隊(duì)列外，還需要專門的區(qū)域存儲(chǔ)有序隊(duì)列。1．問(wèn)題分析直接插入排序然后每次從無(wú)序隊(duì)列中取出一個(gè)元素，先在有序隊(duì)列中找到相應(yīng)的插入位置，再插入到有序隊(duì)列中完成1趟插入，取出一個(gè)元素在有序隊(duì)列中找到相應(yīng)的插入位置插入1．問(wèn)題分析直接插入排序如此反復(fù)，直到無(wú)序隊(duì)列中的元素都取完。取出一個(gè)元素在有序隊(duì)列中找到相應(yīng)的插入位置插入2．算法實(shí)現(xiàn)直接插入排序（1）設(shè)計(jì)main子圖粗框圖。在main子圖中若要調(diào)用其他子程序時(shí)，因子程序還沒(méi)有創(chuàng)建，所以可只畫出空的調(diào)用框，然后給每個(gè)調(diào)用框添加注釋，注明該子程序名字和功能，這樣先有個(gè)總體思路和設(shè)計(jì)，等其他子程序完成后就可回頭補(bǔ)充完善main子圖。2．算法實(shí)現(xiàn)直接插入排序（1）設(shè)計(jì)main子圖粗框圖。main子圖要完成的功能①輸入待排數(shù)據(jù)的個(gè)數(shù)n。①2．算法實(shí)現(xiàn)直接插入排序（1）設(shè)計(jì)main子圖粗框圖。main子圖要完成的功能②調(diào)用一個(gè)輸入子程序input，隨機(jī)產(chǎn)生n個(gè)無(wú)序數(shù)據(jù)存放到數(shù)組a中。②2．算法實(shí)現(xiàn)直接插入排序（1）設(shè)計(jì)main子圖粗框圖。main子圖要完成的功能③調(diào)用一個(gè)輸出子程序output，顯示輸出無(wú)序數(shù)組a中的所有元素。③2．算法實(shí)現(xiàn)直接插入排序（1）設(shè)計(jì)main子圖粗框圖。main子圖要完成的功能④取出a中的第1元素放到有序數(shù)組order[1]中，生成一個(gè)有序數(shù)組order。④2．算法實(shí)現(xiàn)直接插入排序（1）設(shè)計(jì)main子圖粗框圖。main子圖要完成的功能⑤調(diào)用直接插入排序子程序insert進(jìn)行排序。⑤2．算法實(shí)現(xiàn)直接插入排序（1）設(shè)計(jì)main子圖粗框圖。main子圖要完成的功能⑥調(diào)用輸出子程序output，顯示輸出有序數(shù)組order中所有元素。⑥2．算法實(shí)現(xiàn)直接插入排序（2）設(shè)計(jì)輸入和輸出子程序（input、output）。2個(gè)子程序與冒泡排序中的相同，請(qǐng)自行完成。2．算法實(shí)現(xiàn)直接插入排序（3）設(shè)計(jì)直接插入排序子程序insert粗框圖。insert子程序要實(shí)現(xiàn)的就是從無(wú)序隊(duì)列的第2個(gè)元素開(kāi)始取，在有序數(shù)組order中找其插入位置，然后插入，直到無(wú)序隊(duì)列尾部。2．算法實(shí)現(xiàn)直接插入排序（3）設(shè)計(jì)直接插入排序子程序insert粗框圖。根據(jù)功能分析，可在insert子程序中設(shè)計(jì)一個(gè)循環(huán)結(jié)構(gòu)，循環(huán)體內(nèi)調(diào)用一子程序location找a[i]在order中的插入位置，再調(diào)用子程序into將a[i]插入到order中相應(yīng)位置。設(shè)循環(huán)變量為i，從2變化到n2．算法實(shí)現(xiàn)直接插入排序（4）設(shè)計(jì)找插入位置子程序location。location要實(shí)現(xiàn)的功能是找a[i]在order中的插入位置，所以其“輸入”參數(shù)有a、i、order，其中i表示取無(wú)序數(shù)組的第幾個(gè)（i）元素，應(yīng)增加一個(gè)“輸出”參數(shù)wz來(lái)保存找到的插入位置并返回。2．算法實(shí)現(xiàn)直接插入排序（4）設(shè)計(jì)找插入位置子程序location。找插入位置的方法是：將a[i]和order的第1個(gè)元素開(kāi)始比較，如果a[i]大，則再和order中的下一個(gè)元素比較。直到比較到a[i]小了，則order元素所在位置就是插入位置，不用再比較了。若比較到oder的最后一個(gè)元素（下標(biāo)i-1），a[i]都大，則插入位置就是i。2．算法實(shí)現(xiàn)直接插入排序（4）設(shè)計(jì)找插入位置子程序location。所以設(shè)計(jì)一個(gè)循環(huán)結(jié)構(gòu)（設(shè)循環(huán)變量為wz），從order的第1個(gè)元素（wz=1）開(kāi)始，循環(huán)結(jié)束條件有2個(gè)：一個(gè)是a[i]<order[wz]，一個(gè)是到最后1個(gè)元素后（wz>i-1），這兩個(gè)條件用or運(yùn)算符連接。從order的第1個(gè)元素開(kāi)始循環(huán)結(jié)束的2個(gè)條件2．算法實(shí)現(xiàn)直接插入排序（4）設(shè)計(jì)找插入位置子程序location。注意應(yīng)把wz>i-1放在or的左邊，因?yàn)閛r的運(yùn)算順序是“從左到右”，而且左邊表達(dá)式若為“真”，則就不會(huì)再判斷右邊的表達(dá)式，所以應(yīng)先判斷是否到了order的尾部，到了，則不再判斷a[i]<order[wz]。若把a(bǔ)[i]<order[wz]放在左邊，若a[i]一直大，wz就會(huì)超過(guò)order的尾部i-1，先判斷左邊的a[i]<order[wz]時(shí)就會(huì)出現(xiàn)下標(biāo)超出范圍的錯(cuò)誤了。因?yàn)閛r的運(yùn)算順序是“從左到右”2．算法實(shí)現(xiàn)直接插入排序（5）設(shè)計(jì)插入子程序intointo子程序?qū)崿F(xiàn)的功能是將a[i]插入到order中wz的位置處，所以其“輸入”參數(shù)有a、i、order、wz，order同時(shí)也應(yīng)作為“輸出”參數(shù)返回。2．算法實(shí)現(xiàn)直接插入排序（5）設(shè)計(jì)插入子程序into為了不破壞order中的原有元素，在插入之前應(yīng)該先騰出該位置，即:將從order[wz]位置到order尾部的元素都往后移一位，但應(yīng)從最后一個(gè)元素（i-1位置）開(kāi)始后移（移到i位置），i-2位置的元素移到i-1位置，如此反復(fù)，直到wz位置的元素移到wz+1。2．算法實(shí)現(xiàn)直接插入排序（5）設(shè)計(jì)插入子程序into設(shè)計(jì)一個(gè)循環(huán)結(jié)構(gòu)（設(shè)循環(huán)變量為k，從i-1遞減到wz），注意步長(zhǎng)值為-1（即k=k-1）。循環(huán)變量為k，從i-1遞減到wz步長(zhǎng)值為-12．算法實(shí)現(xiàn)直接插入排序（6）完善insert子程序和main子圖找插入位置子程序location和插入子程序into完成后，就可以將其所屬上級(jí)程序insert補(bǔ)充完善完善后的insert子程序2．算法實(shí)現(xiàn)直接插入排序（6）完善insert子程序和main子