一、簡(jiǎn)介
二、步驟
三已慢、示例
四、代碼實(shí)現(xiàn)
struct Node; /* 單鏈表結(jié)點(diǎn)類型 */
typedef int KeyType;
typedef int DataType;
typedef struct Node ListNode;
struct Node {
KeyType key; /* 排序碼字段 */
/*DataType info; 記錄的其它字段 */
ListNode *next; /* 記錄的指針字段 */
};
typedef ListNode * LinkList;
/* 對(duì)鏈表按遞增序進(jìn)行表插入排序霹购，鏈表中第一個(gè)結(jié)點(diǎn)為表頭結(jié)點(diǎn)佑惠。 */
void listSort(LinkList * plist) {
ListNode *now, *pre, *p, *q, *head; head=*plist;
if (head->next == NULL || head->next->next == NULL)
return; /* 為空鏈表或鏈表中只有一個(gè)結(jié)點(diǎn) */
pre = head->next; now = pre->next;
while (now != NULL) {
q = head; p = head->next;
while(p != now && p->key <= now->key) {
q = p; p = p->next;
} /* 本循環(huán)結(jié)束時(shí)，已經(jīng)找到了now的插入位置 */
if (p == now) { /* now應(yīng)放在原位置 */
pre = pre->next; now = pre->next; continue;
}
/* 使now記錄脫鏈齐疙，將now記錄插入鏈表中 */
pre->next = now->next; q->next = now;
now->next = p; now = pre->next;
}
}
ListNode element[9]={
0, &element[1],
49, &element[2],
38, &element[3],
65, &element[4],
97, &element[5],
76, &element[6],
13, &element[7],
27, &element[8],
49, NULL
};
int main(){
LinkList p = element;
listSort(&p);
p = p->next;
while (p != NULL){
printf("%d ",p->key);
p = p->next;
}
getchar();
return 0;
}
五膜楷、評(píng)價(jià)
六、參考資料
插入排序（二）— 表插入排序
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
