7-2插入排序v第七章排序技術(shù)學(xué)什么？直接插入排序希爾排序提出關(guān)鍵問(wèn)題給出解決方法寫出算法描述得到完整算法運(yùn)行實(shí)例7-2-1直接插入排序v第七章排序技術(shù)基本思想在插入第i（i＞1）個(gè)記錄時(shí)，前面的i-1個(gè)記錄已經(jīng)排好序有序區(qū)r1r2ri-1……無(wú)序區(qū)rirnri+1……r'1r'2r'i-1r'i……rnri+1……直接插入排序的基本思想：依次將待排序序列中的每一個(gè)記錄插入到已排好序的序列中，直到全部記錄都排好序。運(yùn)行實(shí)例2420101812122420101812242010181224201018122420101812待排序序列第一趟排序結(jié)果第二趟排序結(jié)果第三趟排序結(jié)果第四趟排序結(jié)果如何構(gòu)造初始的有序序列？242010181212待排序序列for(i=1;i<length;i++){

}將第1個(gè)記錄看成是初始有序序列，然后從第2個(gè)記錄起依次插入到有序序列中，直至將第n個(gè)記錄插入。解決方法：算法描述：插入第i個(gè)記錄，即第i趟直接插入排序；關(guān)鍵問(wèn)題如何將第i

個(gè)記錄插入到有序序列中的合適位置？第一趟排序結(jié)果24201018122010182412242010181212待排序序列關(guān)鍵問(wèn)題242010181212242010181224待排序序列第一趟排序結(jié)果第二趟排序結(jié)果i在有序序列中進(jìn)行順序查找，查找下標(biāo)初始化為多少？jj=i-1;暫存r[i]關(guān)鍵問(wèn)題2420101812122420101812241012待排序序列第一趟排序結(jié)果第二趟排序結(jié)果i在有序序列中進(jìn)行順序查找，循環(huán)條件是什么？temp=data[i];j=i-1;退出循環(huán)，記錄r[i]的最終位置是哪里？data[j+1]=temp;算法描述：while(j>=0&&temp<data[j]){data[j+1]=data[j];j--;}j關(guān)鍵問(wèn)題暫存r[i]算法描述voidSort::InsertSort(){ inti,j,temp;for(i=1;i<length;i++){temp=data[i];j=i-1;while(j>=0&&temp<data[j]){data[j+1]=data[j];j--;}data[j+1]=temp; }}時(shí)間性能比較語(yǔ)句？執(zhí)行次數(shù)？最好情況：n-1次12345最壞情況：2+3+…+n次12345移動(dòng)語(yǔ)句？執(zhí)行次數(shù)？最好情況：2(n-1)次12345voidSort::InsertSort(){ inti,j,temp;for(i=1;i<length;i++){temp=data[i];j=i-1;while(j>=0&&temp<data[j]){data[j+1]=data[j];j--;}data[j+1]=temp; }}最壞情況：3+4+…+n+1次12345時(shí)間性能時(shí)間性能比較次數(shù)：n-1移動(dòng)次數(shù)：2(n-1)

最好情況：正序O(n)最壞情況：逆序比較次數(shù)：移動(dòng)次數(shù)：平均情況：隨機(jī)排列O(n2)O(n2)空間性能時(shí)間性能

空間性能：O(1)

穩(wěn)定性：穩(wěn)定125*454125*455*125*45while(temp<data[j]){data[j+1]=data[j];j--;}7-2-2希爾排序v第七章排序技術(shù)改進(jìn)的著眼點(diǎn)在待排序序列正序時(shí)，直接插入排序的時(shí)間性能是O(n)。當(dāng)待排序的記錄個(gè)數(shù)較多時(shí)，大量的比較和移動(dòng)操作使直接插入排序算法的效率降低。（1）若待排序記錄按關(guān)鍵碼基本有序，直接插入排序的效率較高；改進(jìn)的著眼點(diǎn)：（2）若待排序記錄數(shù)量

n

較小，直接插入排序的效率也很高。待排序記錄數(shù)量n

較大、并不是按關(guān)鍵碼基本有序，怎么辦？基本思想希爾排序的基本思想：將待排序序列分割成若干個(gè)子序列，在子序列內(nèi)分別進(jìn)行直接插入排序，待序列基本有序時(shí)，對(duì)全體記錄進(jìn)行直接插入排序。局部有序（部分有序）不能提高直接插入排序算法的時(shí)間性能?；居行颍航咏?，例如{1,2,8,4,5,6,7,3,9}。{5,6,7,8,9,1,2,3,4}是基本有序嗎？如何分割待排序序列，才能使整個(gè)序列逐步向基本有序發(fā)展？如何分割待排序序列，才能使整個(gè)序列逐步向基本有序發(fā)展？不能是逐段分割，而是將相距某個(gè)增量的記錄組成一個(gè)子序列2408321024*162028123024321624*100812202830基本思想運(yùn)行實(shí)例081024*28321612242030待排序序列增量d=4321612242030081024*28增量d=2321612081024203024*2824203024*2832161008123216120824203024*2810增量d=1關(guān)鍵問(wèn)題希爾排序的基本思想：將待排序序列分割成若干個(gè)子序列，在子序列內(nèi)分別進(jìn)行直接插入排序，待序列基本有序時(shí)，對(duì)全體記錄進(jìn)行直接插入排序。如何分割待排序序列，才能使整個(gè)序列逐步向基本有序發(fā)展？（1）希爾排序的時(shí)間性能取決于增量序列，復(fù)雜的數(shù)學(xué)問(wèn)題。（2）希爾排序是平均時(shí)間性能好于O(n2)的第一批算法之一（1959年）。（3）希爾最早提出的方法是，且增量序列互質(zhì)。顯然最后一個(gè)增量必須等于1——縮小增量排序算法效率與增量序列密切相關(guān)，練習(xí)中一般會(huì)給定增量序列for(d=length/2;d>=1;d=d/2){

}算法描述：以d為增量，在每個(gè)子序列內(nèi)進(jìn)行直接插入排序；關(guān)鍵問(wèn)題希爾排序的基本思想：將待排序序列分割成若干個(gè)子序列，在子序列內(nèi)分別進(jìn)行直接插入排序，待序列基本有序時(shí)，對(duì)全體記錄進(jìn)行直接插入排序。如何分割待排序序列，才能使整個(gè)序列逐步向基本有序發(fā)展？關(guān)鍵問(wèn)題081024*28321612242030待排序序列增量d=4081024*28321612242030i在一趟希爾排序中，從哪個(gè)記錄開(kāi)始執(zhí)行插入操作？for(i=d+1;i<length;i++){

}算法描述：將r[i]插入到所屬子序列的合適位置；081024*28321612242030待排序序列增量d=4081024*28321612242030ij在相應(yīng)子序列中進(jìn)行順序查找，查找下標(biāo)初始化為多少？循環(huán)條件是什么？1632算法描述：temp=r[i];j=i-

d; while(j>=0&&temp<data[j]){data[j+d]=data[j];j=j-d;}關(guān)鍵問(wèn)題081024*28321612242030待排序序列增量d=4081024*28321612242030ij1632退出循環(huán)，記錄r[i]的最終位置是哪里？data[j+d]=temp;16算法描述：temp=r[i];j=i-

d; while(j>=0&&temp<data[j]){data[j+d]=data[j];j=j-d;}關(guān)鍵問(wèn)題驗(yàn)證算法081024*28321612242030待排序序列增量d=4081024*28321612242030ij203216081024*2812242030242032081024*281230直接插入排序時(shí)間性能較好分割使得子序列的記錄個(gè)數(shù)較少16算法實(shí)現(xiàn)voidSort::ShellSort(){ intd,i,j,temp;for(d=length/2;d>=1;d=d/2)//增量為d進(jìn)行直接插入排序{for(i=d;i<length;i++)//進(jìn)行一趟希爾排序{temp=data[i];//暫存待插入記錄for(j=i-d;j>=0&&temp<data[j];j=j-d)data[j+d]=data[j];//記錄后移d個(gè)位置data[j+d]=temp;}}}性能分析（1）希爾排序算法的時(shí)間性能是所取增量的函數(shù)；

時(shí)間性