直接插入排序

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進行比較，將所有關(guā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ù)目較少且基本有序的情況。當待排記錄數(shù)目較大時，直接插入排序的性能就不好，序的情況。當待排記錄數(shù)目較大時，直接插入排序的性能就不好， 為此為此我們可以對直接插入排序做進一步的改進。在直接插入排序法的基礎(chǔ)上，我們可以對直接插入排

7、序做進一步的改進。在直接插入排序法的基礎(chǔ)上，從減少從減少“比較關(guān)鍵字比較關(guān)鍵字”和和“移動記錄移動記錄”兩種操作的次數(shù)著手來進行改進。兩種操作的次數(shù)著手來進行改進。 第第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)鍵字的大小和移動記錄。當原始記錄的序列越接近有序，算法的執(zhí)行效率就越高。當原始記錄的序列越接近有序，算法的執(zhí)行效率就越高。第第10章章 優(yōu)化排序優(yōu)化排序 在算法中，由于待插入元素的比較是從后向前進行的，當遇到關(guān)鍵在算法中，由于待插入元素的比較是從后向前進行的，當遇到關(guān)鍵字小于或等于要插入記錄的關(guān)鍵字就停止操