直接插入排序_第1頁
直接插入排序_第2頁
直接插入排序_第3頁
直接插入排序_第4頁
直接插入排序_第5頁
已閱讀5頁，還剩6頁未讀， 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

數(shù)據(jù)結(jié)構(gòu)北京電子科技職業(yè)學(xué)院目錄直接插入排序直接插入排序?qū)o序子序列中的一個(gè)或幾個(gè)記錄“插入”到有序序列中，從而增加記錄的有序子序列的長度。有序序列r[1..i-1]r[i]

無序序列r[i..n-1]一趟直接插入排序的基本思想：有序序列r[1..i]無序序列r[i+1..n-1]直接插入排序一趟插入排序的基本步驟將R[i]插入到R[j+1]的位置上將R[j+1…i-1]中的所有記錄均后移一個(gè)位置在R[1…i-1]中查找R[i]的插入位置，滿足R[1…j].key<=R[i].key<R[j+1…i-1].key;實(shí)現(xiàn)“一趟插入排序”分為三步直接插入排序不同的位置查找方法導(dǎo)致不同的算法描述：直接插入排序（基于順序查找）折半插入排序（基于折半查找）希爾排序（基于逐趟縮小增量）直接插入排序6利用順序查找實(shí)現(xiàn)在r[1..i-1]中查找r[i]的插入位置從r[i-1]起向前進(jìn)行順序查找，監(jiān)視哨設(shè)置在r[0]；r[0]=r[i];循環(huán)結(jié)束表明r[i]的插入位置為j+1r[0]jr[i]for(j=i-1;r[0].key<r[j].key;--j);j=i-1插入位置直接插入排序?qū)τ谠诓檎疫^程中找到的那些關(guān)鍵字不小于r[i].key的記錄，并在查找的同時(shí)實(shí)現(xiàn)記錄向后移動(dòng)；for(j=i-1;r[0].key<r[j].key;--j)

r[j+1]=r[j]；上述循環(huán)結(jié)束后可以直接進(jìn)行“插入”

r[j+1]=r[0]；直接插入排序令i=2,實(shí)現(xiàn)整個(gè)序列的排序for(i=2;i<=n;i++)if(R[i].key<R[i-1].key){

在R[1…i-1]中查找R[i]的插入位置；插入R[i];}有序序列無序序列i=2i=3i=nR[n]R[3]R[2]3,…,nR[1]直接插入排序voidInsSort(RecordTyper[],intlength){inti,j;for(i=2;i<=length;i++){

r[j+1]=r[0];

/*將待插入記錄插入到已排序的序列中*/}}

r[0]=r[i];

/*將待插入記錄存放到監(jiān)視哨r[0]中*/

j=i-1;while(r[0].key<r[j].key)

/*尋找插入位置*/

{r[j+1]=r[j];j--;}直接插入排序關(guān)鍵字在記

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論