直接插入排序

1、關于直接插入排序第一張，PPT共十九頁，創(chuàng)作于2022年6月教學內(nèi)容： 1、排序的基本概念 2、直接插入排序算法的基本思想 3、直接插入排序算法實現(xiàn) 4、直接插入排序算法性能分析教學重點：直接插入排序算法思想 教學難點：算法實現(xiàn)及性能分析 教學過程 第二張，PPT共十九頁，創(chuàng)作于2022年6月第三張，PPT共十九頁，創(chuàng)作于2022年6月學號姓名學習成績思想政治總分獎學金等次1008XXX2622929111005XXX2502927921003XXX2492827721002XXX2482827621006XXX2432827131007XXX2422726931001XXX231272583

2、1004XXX211272383第四張，PPT共十九頁，創(chuàng)作于2022年6月8.2.1 排序概念排序無序數(shù)據(jù)有序數(shù)據(jù)排序算法主要有：直接插入排序、希爾排序、冒泡排序、快速排序、直接選擇排序、堆排序、歸并排序等。第五張，PPT共十九頁，創(chuàng)作于2022年6月8.2.2 直接插入排序基本思想212549361608i n-1 數(shù)組下標數(shù)組R有序區(qū)無序區(qū)13無序區(qū)第1個元素0 i-1第六張，PPT共十九頁，創(chuàng)作于2022年6月如何確定插入位置？關鍵問題第七張，PPT共十九頁，創(chuàng)作于2022年6月212549360813排序過程臨時變量temp16543201n-1下標第八張，PPT共十九頁，創(chuàng)作于20

3、22年6月流程圖(temp=0)開始temp=Rij=i-1循環(huán)判斷Rj+1=Rjj-Rj=tempNY結束將無序區(qū)中的第一個元素放到臨時變量中j表示有序區(qū)中的最后一個元素的位置將當前元素向后移動有序區(qū)中比較下一個找到插入位置后將第1個元素插入第九張，PPT共十九頁，創(chuàng)作于2022年6月8.2.3 算法實現(xiàn)for (i=1;in;i+) /插入所有元素Void insertsort(arrayType R,int n)int i,j,temp; temp=Ri; /將待排序元素放入臨時變量while(temp=0) Rj+1=Rj; /元素向后移動 j-; /向左繼續(xù)查找 Rj+1=temp;

4、 /將元素插入相應位置 j=i-1; /從Ri-1開始向左查找第十張，PPT共十九頁，創(chuàng)作于2022年6月評價排序算法好壞的標準：一、時間復雜度- 算法執(zhí)行所需要的時間(比較次數(shù) 和移動次數(shù))二、空間復雜度- 算法執(zhí)行所需要的輔助空間個數(shù)主要考慮次要考慮第十一張，PPT共十九頁，創(chuàng)作于2022年6月for (i=1;in;i+)Void insertsort(arrayType R,int n)int i,j,temp; temp While( ) Rj+1=Rj; j-; Rj+1= ; j=i-1;=Ri; R0 2 R0 temp(temp=0)R0Rj浪費時間第十二張，PPT共十九頁，

5、創(chuàng)作于2022年6月第一 進入循環(huán)之前，保存Ri的值第二 在while循環(huán)中“監(jiān)視”下標 是否越界。監(jiān)視哨使用R0的意義第十三張，PPT共十九頁，創(chuàng)作于2022年6月8.2.3 改進后算法insertsort(R)int i,j;for ( ;in;i+) j=i-1; Rj+1=Rj; j-; ; R0=Ri;while(R0Rj)Rj+1=R0i=2第十四張，PPT共十九頁，創(chuàng)作于2022年6月8.2.4 性能分析212549361608131、理想情況第十五張，PPT共十九頁，創(chuàng)作于2022年6月2、最壞情況21254936160813第十六張，PPT共十九頁，創(chuàng)作于2022年6月知識拓展有沒有更好的方法來查找插入位置？簡單、容易實現(xiàn)效率不高查找插入位置的方法不