前兩篇博文，我討論了鏈表的冒泡排序和選擇排序（以Linux內(nèi)核鏈表為例），這篇文章，我想說說插入排序。

一、復(fù)習(xí)數(shù)組的插入排序

插入排序在算法思想中屬于“減治法”。

減治法的基本思想是：規(guī)模為n的原問題的解與較小規(guī)模的子問題的解之間具有某種關(guān)系。由于存在這種關(guān)系，所以只需求解其中一個(gè)較小規(guī)模的子問題就可以得到原問題的解。

插入排序就是基于“減治法”中的“減一技術(shù)”實(shí)現(xiàn)的。如果題目要求對(duì)a[0]到a[n-1]進(jìn)行排序，我幻想從a[0]到a[n-2]已經(jīng)是有序的了，那么我需要做的就是在這些有序的元素中為a[n-1]找到一個(gè)合適的位置，然后把它插到那里就行。

雖然插入排序基于遞歸思想，可從頂至下實(shí)現(xiàn)；但是，從底至上地實(shí)現(xiàn)這個(gè)算法——使用迭代會(huì)效率更高。從a[1]開始，到a[n-1]為止，a[i]被插入到數(shù)組的前i個(gè)有序元素中的適當(dāng)位置上（但是，和選擇排序不同，這個(gè)位置一般來說并不是它的最終位置）。

示意圖如下：

二、內(nèi)核鏈表的插入排序

完整代碼如下。（list.h文件這里就不列了，有需要的話可以參考我的博文http://blog.csdn.net/longintchar/article/details/78034827）

#include <stdio.h> #include "list.h"struct data_info {int data;struct list_head list; };int cmp_data(struct list_head *a, struct list_head *b) {struct data_info *pa = list_entry(a, struct data_info, list);struct data_info *pb = list_entry(b, struct data_info, list);return pa->data - pb->data; }void swap(struct list_head *a, struct list_head *b) {struct list_head flag = {NULL, NULL};__list_add(&flag, b->prev, b);list_del(b);__list_add(b, a->prev, a);list_del(a);__list_add(a, flag.prev, &flag);list_del(&flag); }void insert_sort(struct list_head *head, int(*cmp)(struct list_head *a, struct list_head *b)) {struct list_head *i, *j,*temp;i = head->next->next; //i指向第2個(gè)結(jié)點(diǎn)list_for_each_from(i,head){ //i從第2個(gè)結(jié)點(diǎn)開始遍歷,因?yàn)榈?個(gè)已經(jīng)有序j = i->prev; //j指向i的前一個(gè)結(jié)點(diǎn)if (cmp(j, i) <= 0) //從表頭開始，按照升序排列continue;list_for_each_reverse_continue(j,head){ if(cmp(j,i) <= 0)break;}temp = i->next; //因?yàn)橄挛囊獎(jiǎng)h除i結(jié)點(diǎn)，所以記錄i結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)list_del(i);__list_add(i,j,j->next); //把i插入到j(luò)的后面i = temp->prev; //i指針歸位} }int main(void) {struct data_info s[] = {{6}, {4}, {7}, {9}, {2}, {8}, {5}, {1}, {3}, {7}};LIST_HEAD(head);int i;for (i = 0; i < sizeof s/ sizeof *s; ++i) {list_add_tail(&s[i].list, &head);} //尾插，構(gòu)成鏈表struct data_info *pdata = NULL;list_for_each_entry(pdata, &head, list) {printf("%d ", pdata->data);}printf("\n"); //排序之前insert_sort(&head, cmp_data); //進(jìn)行排序list_for_each_entry(pdata, &head, list) {printf("%d ", pdata->data);}printf("\n"); //排序之后return 0; }

以上代碼運(yùn)行結(jié)果如下：

6 4 7 9 2 8 5 1 3 7
1 2 3 4 5 6 7 7 8 9

三、代碼解析

1. swap函數(shù)

可以參考我的博文http://blog.csdn.net/longintchar/article/details/78638975

2. list_for_each_from宏

#define list_for_each_from(cur, head) \for (; cur != head; cur = (cur)->next)

這個(gè)宏表示從當(dāng)前結(jié)點(diǎn)開始遍歷，一直到鏈表尾端。

3. list_for_each_reverse_continue宏

#define list_for_each_reverse_continue(cur, head) \for (cur = (cur)->prev; cur != (head); cur = (cur)->prev)

這個(gè)宏表示從當(dāng)前結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)開始，逆序遍歷，一直到第一個(gè)結(jié)點(diǎn)。

4. __list_add函數(shù)

static inline void __list_add(struct list_head *new,struct list_head *prev,struct list_head *next) {next->prev = new;new->next = next;new->prev = prev;prev->next = new; }

把new指向的結(jié)點(diǎn)插入到prev和next結(jié)點(diǎn)之間。

5. insert_sort函數(shù)

void insert_sort(struct list_head *head, int(*cmp)(struct list_head *a, struct list_head *b)) {struct list_head *i, *j,*temp;i = head->next->next; //i指向第2個(gè)結(jié)點(diǎn)list_for_each_from(i,head){ //i從第2個(gè)結(jié)點(diǎn)開始遍歷,因?yàn)榈?個(gè)已經(jīng)有序j = i->prev; //j指向i的前一個(gè)結(jié)點(diǎn)if (cmp(j, i) <= 0) //從表頭開始，按照升序排列continue;list_for_each_reverse_continue(j,head){ if(cmp(j,i) <= 0)break;}temp = i->next; //因?yàn)橄挛囊獎(jiǎng)h除i結(jié)點(diǎn)，所以記錄i結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)list_del(i);__list_add(i,j,j->next); //把i插入到j(luò)的后面i = temp->prev; //i指針歸位} }

6~7行：i從第二個(gè)結(jié)點(diǎn)開始，一直遍歷到最后一個(gè)結(jié)點(diǎn)；
第10行：j指向i結(jié)點(diǎn)的前驅(qū)，如果j結(jié)點(diǎn)小于等于i結(jié)點(diǎn)，說明i不需要插入，它已經(jīng)在合適的位置（不一定是最終位置）上了，此時(shí)進(jìn)入下一輪迭代；
第12~14行：能執(zhí)行到第12行，說明j結(jié)點(diǎn)大于i結(jié)點(diǎn)，這時(shí)候我們要做的是——從j向前找，找到第一個(gè)小于等于i的結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)用j指示。找到后跳出這層循環(huán)。
17~18行：我們需要把i結(jié)點(diǎn)插入到j(luò)的后面。
16和19行：因?yàn)閕結(jié)點(diǎn)移動(dòng)了，所以i指針需要?dú)w位，第16行記錄了i結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，叫temp，第19行讓i指向temp的前驅(qū)，完成歸位。為什么要?dú)w位？可以參考我的博文 http://blog.csdn.net/longintchar/article/details/78638975 中的4.4節(jié)。

【完】

總結(jié)

以上是生活随笔為你收集整理的双向循环链表的插入排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。