直接插入排序

關(guān)于直接插入排序第1頁(yè)，課件共19頁(yè)，創(chuàng)作于2023年2月教學(xué)內(nèi)容：

1、排序的基本概念

2、直接插入排序算法的基本思想

3、直接插入排序算法實(shí)現(xiàn)

4、直接插入排序算法性能分析教學(xué)重點(diǎn)：直接插入排序算法思想

教學(xué)難點(diǎn)：算法實(shí)現(xiàn)及性能分析

教學(xué)過(guò)程

第2頁(yè)，課件共19頁(yè)，創(chuàng)作于2023年2月第3頁(yè)，課件共19頁(yè)，創(chuàng)作于2023年2月學(xué)號(hào)姓名學(xué)習(xí)成績(jī)思想政治總分獎(jiǎng)學(xué)金等次1008XXX2622929111005XXX2502927921003XXX2492827721002XXX2482827621006XXX2432827131007XXX2422726931001XXX2312725831004XXX211272383………………第4頁(yè)，課件共19頁(yè)，創(chuàng)作于2023年2月8.2.1排序概念排序無(wú)序數(shù)據(jù)有序數(shù)據(jù)排序算法主要有：直接插入排序、希爾排序、冒泡排序、快速排序、直接選擇排序、堆排序、歸并排序等。第5頁(yè)，課件共19頁(yè)，創(chuàng)作于2023年2月8.2.2直接插入排序基本思想212549361608i…n-1數(shù)組下標(biāo)數(shù)組R有序區(qū)無(wú)序區(qū)13無(wú)序區(qū)第1個(gè)元素……0…

i-1第6頁(yè)，課件共19頁(yè)，創(chuàng)作于2023年2月如何確定插入位置？關(guān)鍵問(wèn)題第7頁(yè)，課件共19頁(yè)，創(chuàng)作于2023年2月212549360813排序過(guò)程臨時(shí)變量temp16543201…n-1下標(biāo)…第8頁(yè)，課件共19頁(yè)，創(chuàng)作于2023年2月流程圖(temp<R[j])&&(j>=0)開始temp=R[i]j=i-1循環(huán)判斷R[j+1]=R[j]j--R[j]=tempNY結(jié)束將無(wú)序區(qū)中的第一個(gè)元素放到臨時(shí)變量中j表示有序區(qū)中的最后一個(gè)元素的位置將當(dāng)前元素向后移動(dòng)有序區(qū)中比較下一個(gè)找到插入位置后將第1個(gè)元素插入第9頁(yè)，課件共19頁(yè)，創(chuàng)作于2023年2月8.2.3算法實(shí)現(xiàn)for(i=1;i<n;i++){//插入所有元素Voidinsertsort(arrayTypeR[],intn){inti,j,temp;temp=R[i];//將待排序元素放入臨時(shí)變量while((temp<R[j])&&(j>=0)){R[j+1]=R[j];//元素向后移動(dòng)j--;//向左繼續(xù)查找

}R[j+1]=temp;//將元素插入相應(yīng)位置

}j=i-1;//從R[i-1]開始向左查找}第10頁(yè)，課件共19頁(yè)，創(chuàng)作于2023年2月評(píng)價(jià)排序算法好壞的標(biāo)準(zhǔn)：一、時(shí)間復(fù)雜度-算法執(zhí)行所需要的時(shí)間(比較次數(shù)和移動(dòng)次數(shù))二、空間復(fù)雜度-算法執(zhí)行所需要的輔助空間個(gè)數(shù)主要考慮次要考慮第11頁(yè)，課件共19頁(yè)，創(chuàng)作于2023年2月for(i=1;i<n;i++){Voidinsertsort(arrayTypeR[],intn){inti,j,temp;tempWhile(

){R[j+1]=R[j];j--;}R[j+1]=;}j=i-1;}=R[i];R[0]2R[0]temp(temp<R[j])&&(j>=0)R[0]<R[j]浪費(fèi)時(shí)間第12頁(yè)，課件共19頁(yè)，創(chuàng)作于2023年2月第一進(jìn)入循環(huán)之前，保存R[i]的值第二在while循環(huán)中“監(jiān)視”下標(biāo)是否越界。監(jiān)視哨使用R[0]的意義第13頁(yè)，課件共19頁(yè)，創(chuàng)作于2023年2月8.2.3改進(jìn)后算法insertsort(R){inti,j;for(;i<n;i++){

j=i-1;

{R[j+1]=R[j];j--;}

;}}

R[0]=R[i];while(R[0]<R[j])R[j+1]=R[0]i=2第14頁(yè)，課件共19頁(yè)，創(chuàng)作于2023年2月8.2.4性能分析212549361608131、理想情況第15頁(yè)，課件共19頁(yè)，創(chuàng)作于2023年2月2、最壞情況21254936160813第16頁(yè)，課件共19頁(yè)，創(chuàng)作于2023年2月知識(shí)拓展有沒(méi)有更好的方法來(lái)查找