




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
1、第十章第十章 優(yōu)化排序優(yōu)化排序直接插入排序第第10章章 優(yōu)化排序優(yōu)化排序插入排序插入排序 插入排序的基本思想是:在一個已排好序的記錄子集的基礎(chǔ)上,每插入排序的基本思想是:在一個已排好序的記錄子集的基礎(chǔ)上,每一步將下一個待排序的記錄有序地插入到已排好序的記錄子集中,直到一步將下一個待排序的記錄有序地插入到已排好序的記錄子集中,直到將所有待排記錄全部插入為止。將所有待排記錄全部插入為止。 打撲克牌時的抓牌就是插入排序一個很好的例子,每抓一張牌,插打撲克牌時的抓牌就是插入排序一個很好的例子,每抓一張牌,插入到合適位置,直到抓完牌為止,即可得到一個有序序列。入到合適位置,直到抓完牌為止,即可得到一個有
2、序序列。 第第10章章 優(yōu)化排序優(yōu)化排序直接插入排序直接插入排序 直接插入排序是一種最基本的插入排序方法。其基本操作是將第直接插入排序是一種最基本的插入排序方法。其基本操作是將第i個記錄插入到前面?zhèn)€記錄插入到前面i-1個已排好序的記錄中,具體過程為:個已排好序的記錄中,具體過程為: 將第將第i個記錄的關(guān)鍵字個記錄的關(guān)鍵字Ki順次與其前面記錄的關(guān)鍵字順次與其前面記錄的關(guān)鍵字Ki-1,Ki-2,, K1進(jìn)行比較,將所有關(guān)鍵字大于進(jìn)行比較,將所有關(guān)鍵字大于Ki的記錄依次向后移動一個位置,直到遇見的記錄依次向后移動一個位置,直到遇見一個關(guān)鍵字小于或者等于一個關(guān)鍵字小于或者等于Ki的記錄的記錄Kj,此時
3、,此時Kj后面必為空位置,將第后面必為空位置,將第i個記錄插入空位置即個記錄插入空位置即可。完整的直接插入排序是從可。完整的直接插入排序是從i=2開始的,也就是說,將第開始的,也就是說,將第1個記錄視為已排好序的單元素個記錄視為已排好序的單元素子集合,然后將第子集合,然后將第2個記錄插入到單元素子集合中。個記錄插入到單元素子集合中。i從從2循環(huán)到循環(huán)到n,即可實現(xiàn)完整的直接插,即可實現(xiàn)完整的直接插入排序。入排序。第第10章章 優(yōu)化排序優(yōu)化排序例例 設(shè)有一組關(guān)鍵字序列設(shè)有一組關(guān)鍵字序列43,21,89,15, ,28,這里,這里n=6,即有,即有6個記錄。請將其按由小到大的順序排序。個記錄。請將
4、其按由小到大的順序排序。 894343282115)28(6288943432115)43(5284389432115)15(4284315894321)89(3284315894321)21(2284315892143()654 32 1 0iiiiirrrrrrr初始關(guān)鍵字43第第10章章 優(yōu)化排序優(yōu)化排序 假設(shè)待排序記錄存放在假設(shè)待排序記錄存放在r1.n之中,為了提高效率,我們附設(shè)一個之中,為了提高效率,我們附設(shè)一個監(jiān)視哨監(jiān)視哨r0,使得,使得r0始終存放待插入的記錄。監(jiān)視哨的作用有兩個:一始終存放待插入的記錄。監(jiān)視哨的作用有兩個:一是備份待插入的記錄,以便前面關(guān)鍵字較大的記錄后移;二是
5、防止越界,是備份待插入的記錄,以便前面關(guān)鍵字較大的記錄后移;二是防止越界,具體算法描述如下:具體算法描述如下: 第第10章章 優(yōu)化排序優(yōu)化排序void InsertSort(RecordType r,int n) int i,j; for(i=2;in;i+) /執(zhí)行了執(zhí)行了n-2次次 if (ri.keyri-1.key) r0=ri; j=i-1; /將帶插入記錄存放到監(jiān)視哨中將帶插入記錄存放到監(jiān)視哨中 while(r0.keyrj.key) /尋找插入位置尋找插入位置 rj+1=rj; j=j-1; /記錄后移記錄后移 rj+1=r0 /將待插入記錄插入正確位置將待插入記錄插入正確位置
6、第第10章章 優(yōu)化排序優(yōu)化排序該算法的要點是該算法的要點是: 使用監(jiān)視哨使用監(jiān)視哨r0臨時保存待插入的記錄;臨時保存待插入的記錄; 從后往前查找應(yīng)插入的位置;從后往前查找應(yīng)插入的位置; 查找與移動在同一循環(huán)中完成。查找與移動在同一循環(huán)中完成。第第10章章 優(yōu)化排序優(yōu)化排序 直接插入排序算法簡便,比較適用于待排序記錄數(shù)目較少且基本有直接插入排序算法簡便,比較適用于待排序記錄數(shù)目較少且基本有序的情況。當(dāng)待排記錄數(shù)目較大時,直接插入排序的性能就不好,序的情況。當(dāng)待排記錄數(shù)目較大時,直接插入排序的性能就不好, 為此為此我們可以對直接插入排序做進(jìn)一步的改進(jìn)。在直接插入排序法的基礎(chǔ)上,我們可以對直接插入排
7、序做進(jìn)一步的改進(jìn)。在直接插入排序法的基礎(chǔ)上,從減少從減少“比較關(guān)鍵字比較關(guān)鍵字”和和“移動記錄移動記錄”兩種操作的次數(shù)著手來進(jìn)行改進(jìn)。兩種操作的次數(shù)著手來進(jìn)行改進(jìn)。 第第10章章 優(yōu)化排序優(yōu)化排序從空間分析來看,它只需要一個記錄的輔助空間,空間復(fù)雜度為從空間分析來看,它只需要一個記錄的輔助空間,空間復(fù)雜度為O(1)。)。從時間分析來看,外循環(huán)從時間分析來看,外循環(huán)for執(zhí)行了執(zhí)行了n-1次,每次循環(huán)的基本操作為次,每次循環(huán)的基本操作為:比較比較兩個關(guān)鍵字的大小和移動記錄。兩個關(guān)鍵字的大小和移動記錄。當(dāng)原始記錄的序列越接近有序,算法的執(zhí)行效率就越高。當(dāng)原始記錄的序列越接近有序,算法的執(zhí)行效率就越高。第第10章章 優(yōu)化排序優(yōu)化排序 在算法中,由于待插入元素的比較是從后向前進(jìn)行的,當(dāng)遇到關(guān)鍵在算法中,由于待插入元素的比較是從后向前進(jìn)行的,當(dāng)遇到關(guān)鍵字小于或等于要插入記錄的關(guān)鍵字就停止操
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 臺州科技職業(yè)學(xué)院《病原與宿主防御(含免疫、微生物、寄生蟲)》2023-2024學(xué)年第二學(xué)期期末試卷
- 朔州陶瓷職業(yè)技術(shù)學(xué)院《英語新聞閱讀與思辨》2023-2024學(xué)年第二學(xué)期期末試卷
- 聯(lián)鎖品牌策劃方案(3篇)
- 植被管理方案模板(3篇)
- 廢棄糧庫改造方案(3篇)
- 機(jī)房設(shè)施維修方案(3篇)
- 無創(chuàng)呼吸機(jī)火災(zāi)應(yīng)急預(yù)案(3篇)
- 機(jī)房線路整改方案(3篇)
- 大班多元整合教學(xué)課件
- 電器展臺投標(biāo)方案(3篇)
- 腹部血管解剖詳解課件
- 外來物種對生物多樣性影響課件
- 2023版初中化學(xué)跨學(xué)科實踐活動(化學(xué))
- 醫(yī)院職工代表大會暨工會會員代表大會提案表
- Oxford-3000-牛津核心詞匯
- 散打裁判的基本手勢
- 《延安我把你追尋》課件
- 石材產(chǎn)品質(zhì)量保證書
- 兒童意外傷害預(yù)防-ppt課件
- 衰老生物學(xué)ppt課件(PPT 57頁)
- 外研版必修二短語(教師版)
評論
0/150
提交評論