直接插入排序

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

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

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

4、 /將元素插入相應(yīng)位置 j=i-1; /從Ri-1開始向左查找第十張，PPT共十九頁(yè)，創(chuàng)作于2022年6月評(píng)價(jià)排序算法好壞的標(biāo)準(zhǔn)：一、時(shí)間復(fù)雜度- 算法執(zhí)行所需要的時(shí)間(比較次數(shù) 和移動(dòng)次數(shù))二、空間復(fù)雜度- 算法執(zhí)行所需要的輔助空間個(gè)數(shù)主要考慮次要考慮第十一張，PPT共十九頁(yè)，創(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浪費(fèi)時(shí)間第十二張，PPT共十九頁(yè)，

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