表插入排序算法分析：

　　直接插入排序、折半插入排序均要大量移動(dòng)記錄，時(shí)間開(kāi)銷(xiāo)大。若要不移動(dòng)記錄完成排序，需要改變存儲(chǔ)結(jié)構(gòu)，進(jìn)行表插入排序。所謂表插入排序，就是通過(guò)鏈接指針，按關(guān)鍵碼的大小，實(shí)現(xiàn)從小到大的鏈接過(guò)程，為此需增設(shè)一個(gè)指針項(xiàng)。操作方法與直接插入排序類(lèi)似，所不同的是直接插入排序要移動(dòng)記錄，而表插入排序是修改鏈接指針。用靜態(tài)鏈表來(lái)說(shuō)明。

　　#define SIZE 200

　　typedef struct{

　　ElemType elem; /*元素類(lèi)型*/

　　int next; /*指針項(xiàng)*/

　　}NodeType; /*表結(jié)點(diǎn)類(lèi)型*/

　　typedef struct{

　　NodeType r[SIZE]; /*靜態(tài)鏈表*/

　　int length; /*表長(zhǎng)度*/

　　}L_TBL; /*靜態(tài)鏈表類(lèi)型*/

　　假設(shè)數(shù)據(jù)元素已存儲(chǔ)在鏈表中，且0號(hào)單元作為頭結(jié)點(diǎn)，不移動(dòng)記錄而只是改變鏈指針域，將記錄按關(guān)鍵碼建為一個(gè)有序鏈表。首先，設(shè)置空的循環(huán)鏈表，即頭結(jié)點(diǎn)指針域置0，并在頭結(jié)點(diǎn)數(shù)據(jù)域中存放比所有記錄關(guān)鍵碼都大的整數(shù)。接下來(lái)，逐個(gè)結(jié)點(diǎn)向鏈表中插入即可。

　　表插入排序得到一個(gè)有序的鏈表，查找則只能進(jìn)行順序查找，而不能進(jìn)行隨機(jī)查找，如折半查找。為此，還需要對(duì)記錄進(jìn)行重排。

　　重排記錄方法：按鏈表順序掃描各結(jié)點(diǎn)，將第i個(gè)結(jié)點(diǎn)中的數(shù)據(jù)元素調(diào)整到數(shù)組的第i個(gè)分量數(shù)據(jù)域。因?yàn)榈趇個(gè)結(jié)點(diǎn)可能是數(shù)組的第j個(gè)分量，數(shù)據(jù)元素調(diào)整僅需將兩個(gè)數(shù)組分量中數(shù)據(jù)元素交換即可，但為了能對(duì)所有數(shù)據(jù)元素進(jìn)行正常調(diào)整，指針域也需處理。

　　【算法10.3】

　　1. j=l->r[0].next;i=1; //指向第一個(gè)記錄位置，從第一個(gè)記錄開(kāi)始調(diào)整

　　2. 若i=l->length時(shí)，調(diào)整結(jié)束;否則，

　　a. 若i=j，j=l->r[j].next;i++;轉(zhuǎn)(2) //數(shù)據(jù)元素應(yīng)在這分量中，不用調(diào)整，處理下一個(gè)結(jié)點(diǎn)

　　b. 若j>i，l->r[i].elem<-->l->r[j].elem; //交換數(shù)據(jù)元素

　　p=l->r[j].next; // 保存下一個(gè)結(jié)點(diǎn)地址

　　l->r[j].next=l->[i].next;l->[i].next=j; // 保持后續(xù)鏈表不被中斷

　　j=p;i++;轉(zhuǎn)(2) // 指向下一個(gè)處理的結(jié)點(diǎn)

　　c. 若jr[j].next;//j分量中原記錄已移走，沿j的指針域找尋原記錄的位置

　　轉(zhuǎn)到(a)

　　【時(shí)效分析】

　　表插入排序的基本操作是將一個(gè)記錄插入到已排好序的有序鏈表中，設(shè)有序表長(zhǎng)度為i，則需要比較至多i+1次，修改指針兩次。因此，總比較次數(shù)與直接插入排序相同，修改指針總次數(shù)為2n次。所以，時(shí)間復(fù)雜度仍為O(n2)

　　　　　　　計(jì)算機(jī)軟考軟件設(shè)計(jì)師練習(xí)試題及答案解析匯總