大學計算機基礎 課件 10.3.3直接插入排序

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