直接插入排序

1、第十章第十章 優(yōu)化排序優(yōu)化排序直接插入排序第第10章章 優(yōu)化排序優(yōu)化排序插入排序插入排序 插入排序的基本思想是：在一個(gè)已排好序的記錄子集的基礎(chǔ)上，每插入排序的基本思想是：在一個(gè)已排好序的記錄子集的基礎(chǔ)上，每一步將下一個(gè)待排序的記錄有序地插入到已排好序的記錄子集中，直到一步將下一個(gè)待排序的記錄有序地插入到已排好序的記錄子集中，直到將所有待排記錄全部插入為止。將所有待排記錄全部插入為止。 打撲克牌時(shí)的抓牌就是插入排序一個(gè)很好的例子，每抓一張牌，插打撲克牌時(shí)的抓牌就是插入排序一個(gè)很好的例子，每抓一張牌，插入到合適位置，直到抓完牌為止，即可得到一個(gè)有序序列。入到合適位置，直到抓完牌為止，即可得到一個(gè)有

2、序序列。 第第10章章 優(yōu)化排序優(yōu)化排序直接插入排序直接插入排序 直接插入排序是一種最基本的插入排序方法。其基本操作是將第直接插入排序是一種最基本的插入排序方法。其基本操作是將第i個(gè)記錄插入到前面?zhèn)€記錄插入到前面i-1個(gè)已排好序的記錄中，具體過程為：個(gè)已排好序的記錄中，具體過程為： 將第將第i個(gè)記錄的關(guān)鍵字個(gè)記錄的關(guān)鍵字Ki順次與其前面記錄的關(guān)鍵字順次與其前面記錄的關(guān)鍵字Ki-1，Ki-2，, K1進(jìn)行比較，將所有關(guān)鍵字大于進(jìn)行比較，將所有關(guān)鍵字大于Ki的記錄依次向后移動(dòng)一個(gè)位置，直到遇見的記錄依次向后移動(dòng)一個(gè)位置，直到遇見一個(gè)關(guān)鍵字小于或者等于一個(gè)關(guān)鍵字小于或者等于Ki的記錄的記錄Kj，此時(shí)

3、，此時(shí)Kj后面必為空位置，將第后面必為空位置，將第i個(gè)記錄插入空位置即個(gè)記錄插入空位置即可。完整的直接插入排序是從可。完整的直接插入排序是從i=2開始的，也就是說，將第開始的，也就是說，將第1個(gè)記錄視為已排好序的單元素個(gè)記錄視為已排好序的單元素子集合，然后將第子集合，然后將第2個(gè)記錄插入到單元素子集合中。個(gè)記錄插入到單元素子集合中。i從從2循環(huán)到循環(huán)到n，即可實(shí)現(xiàn)完整的直接插，即可實(shí)現(xiàn)完整的直接插入排序。入排序。第第10章章 優(yōu)化排序優(yōu)化排序例例 設(shè)有一組關(guān)鍵字序列設(shè)有一組關(guān)鍵字序列43，21，89，15， ，28，這里，這里n=6，即有，即有6個(gè)記錄。請(qǐng)將其按由小到大的順序排序。個(gè)記錄。請(qǐng)將

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è)一個(gè)之中，為了提高效率，我們附設(shè)一個(gè)監(jiān)視哨監(jiān)視哨r0，使得，使得r0始終存放待插入的記錄。監(jiān)視哨的作用有兩個(gè)：一始終存放待插入的記錄。監(jiān)視哨的作用有兩個(gè)：一是備份待插入的記錄，以便前面關(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)化排序該算法的要點(diǎn)是該算法的要點(diǎn)是： 使用監(jiān)視哨使用監(jiān)視哨r0臨時(shí)保存待插入的記錄；臨時(shí)保存待插入的記錄； 從后往前查找應(yīng)插入的位置；從后往前查找應(yīng)插入的位置； 查找與移動(dòng)在同一循環(huán)中完成。查找與移動(dòng)在同一循環(huán)中完成。第第10章章 優(yōu)化排序優(yōu)化排序 直接插入排序算法簡便，比較適用于待排序記錄數(shù)目較少且基本有直接插入排序算法簡便，比較適用于待排序記錄數(shù)目較少且基本有序的情況。當(dāng)待排記錄數(shù)目較大時(shí)，直接插入排序的性能就不好，序的情況。當(dāng)待排記錄數(shù)目較大時(shí)，直接插入排序的性能就不好， 為此為此我們可以對(duì)直接插入排序做進(jìn)一步的改進(jìn)。在直接插入排序法的基礎(chǔ)上，我們可以對(duì)直接插入排

7、序做進(jìn)一步的改進(jìn)。在直接插入排序法的基礎(chǔ)上，從減少從減少“比較關(guān)鍵字比較關(guān)鍵字”和和“移動(dòng)記錄移動(dòng)記錄”兩種操作的次數(shù)著手來進(jìn)行改進(jìn)。兩種操作的次數(shù)著手來進(jìn)行改進(jìn)。 第第10章章 優(yōu)化排序優(yōu)化排序從空間分析來看，它只需要一個(gè)記錄的輔助空間，空間復(fù)雜度為從空間分析來看，它只需要一個(gè)記錄的輔助空間，空間復(fù)雜度為O（1）。）。從時(shí)間分析來看，外循環(huán)從時(shí)間分析來看，外循環(huán)for執(zhí)行了執(zhí)行了n-1次，每次循環(huán)的基本操作為次，每次循環(huán)的基本操作為:比較比較兩個(gè)關(guān)鍵字的大小和移動(dòng)記錄。兩個(gè)關(guān)鍵字的大小和移動(dòng)記錄。當(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)鍵字就停止操