直接插入排序

直接插入排序第一頁，共18頁。教學(xué)內(nèi)容：

1、排序的基本概念

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

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

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

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

教學(xué)過程

第二頁，共18頁。第三頁，共18頁。學(xué)號姓名學(xué)習(xí)成績思想政治總分獎學(xué)金等次1008XXX2622929111005XXX2502927921003XXX2492827721002XXX2482827621006XXX2432827131007XXX2422726931001XXX2312725831004XXX211272383………………第四頁，共18頁。8.2.1排序概念排序無序數(shù)據(jù)有序數(shù)據(jù)排序算法主要有：直接插入排序、希爾排序、冒泡排序、快速排序、直接選擇排序、堆排序、歸并排序等。第五頁，共18頁。8.2.2直接插入排序基本思想212549361608i…n-1數(shù)組下標(biāo)數(shù)組R有序區(qū)無序區(qū)13無序區(qū)第1個元素……0…

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

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

}j=i-1;//從R[i-1]開始向左查找}第十頁，共18頁。評價排序算法好壞的標(biāo)準(zhǔn)：一、時間復(fù)雜度-算法執(zhí)行所需要的時間(比較次數(shù)和移動次數(shù))二、空間復(fù)雜度-算法執(zhí)行所需要的輔助空間個數(shù)主要考慮次要考慮第十一頁，共18頁。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]浪費時間第十二頁，共18頁。第一進(jìn)入循環(huán)之前，保存R[i]的值第二在while循環(huán)中“監(jiān)視”下標(biāo)是否越界。監(jiān)視哨使用R[0]的意義第十三頁，共18頁。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第十四頁，共18頁。8.2.4性能分析212549361608131、理想情況第十五頁，共18頁。2、最壞情況21254