一、復習數(shù)組的冒泡排序

http://blog.csdn.net/longintchar/article/details/75710000
上面這篇博文我介紹了數(shù)組的冒泡排序。

冒泡排序屬于蠻力法，它比較表中的相鄰元素，如果它們是逆序的話就交換它們的位置。重復多次后，最終，最大的元素就“冒”到列表的最后一個位置。第二遍操作將第二大的元素“冒”出來。這樣一直重復，直到n-1遍（假設列表共有n個元素）以后，該列表就排序好了。

示意圖如下所示：

從上圖中的start（最左邊）開始，向右兩兩比較，比較一輪后，最大的數(shù)冒到最右邊，占據end的位置；
end向左移動一個位置，再從start（最左邊）開始，向右兩兩比較……
三輪過后，4個數(shù)就排序OK了。

數(shù)組的冒泡排序代碼如下：

void bubble_sort(int *arr, int len) {int start;int end;for (end=len-1; end>0; end--) {for (start=0; start<end; ++start) {if(arr[start] > arr[start+1])swap(arr+start, arr+start+1); }} }

二、復習內核鏈表

既然是鏈表的排序，那肯定要有鏈表。用別人造好的輪子當然是最省時省力的辦法，不如我們把Linux內核鏈表拿來用用吧。

下文要用到的函數(shù)如下：

1. 結點的插入

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; }

__list_add這個函數(shù)表示把新結點插入到prev和next之間。

2. 結點的刪除

static inline void __list_del(struct list_head * prev, struct list_head * next) {next->prev = prev;prev->next = next; }static inline void list_del(struct list_head *entry) {__list_del(entry->prev, entry->next); }

list_del用來刪除某個結點。

3.遍歷和逆向遍歷

#define list_for_each(pos, head) \for (pos = (head)->next; pos != (head); pos = pos->next)#define list_for_each_reverse(cur, head) \for (cur = (head)->prev; cur != head; cur = (cur)->prev) //內核源碼好像沒有這個宏，我們可以自己加上

另外，還用到了一些函數(shù)，由于經常用，這里就不貼了。源碼可以參考我的博文 http://blog.csdn.net/longintchar/article/details/78034827

三、排序完整代碼

#include <stdio.h> #include "list.h" //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 bubble_sort(struct list_head *head, int (*compar)(struct list_head *, struct list_head *)) {struct list_head *start = NULL; struct list_head *end = NULL; list_for_each_reverse(end, head) { list_for_each(start, head) { if (start == end) break;if (compar(start, start->next) > 0) {swap(start, start->next); start = start->prev; //start歸位if (start == end) end = end->next; //end歸位 }}} }int main(void) {struct data_info s[] = {{6}, {4}, {7}, {9}, {2}, {8}, {5}, {1}, {3}};LIST_HEAD(head);int i;for (i = 0; i < sizeof s/ sizeof *s; ++i) {list_add_tail(&s[i].list, &head);} //尾插，構成鏈表struct data_info *pdata = NULL;list_for_each_entry(pdata, &head, list) {printf("%d ", pdata->data);}printf("\n"); //排序之前bubble_sort(&head, cmp_data); //進行排序list_for_each_entry(pdata, &head, list) {printf("%d ", pdata->data);}printf("\n"); //排序之后return 0; }

運行結果如下：

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

四、代碼解析

1.比較大小是一個函數(shù)指針

排序函數(shù)的原型是:

void bubble_sort(struct list_head *head, int (*compar)(struct list_head *, struct list_head *))

第一個參數(shù)是鏈表的頭結點（指針），第二個參數(shù)是指向函數(shù)的指針，這個函數(shù)由用戶定義。因為數(shù)據類型是用戶定義的，所以只有用戶才清楚如何比較數(shù)據。
本代碼中，我們定義的鏈表元素是整數(shù)，比較大小也很簡單，直接相減就可以了。

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; }

2.交換函數(shù)

冒泡排序就是靠一輪輪的比較和交換，比較前文說過了，不是難點，那么如何交換呢？

仔細想想，這個交換還是挺麻煩的。有人說，把a結點的數(shù)據域和b結點的數(shù)據域交換就可以了。這是一個辦法，優(yōu)點是不用移動結點，單純拷貝數(shù)據域就行；缺點是不夠通用，因為你無法預知用戶定義的是什么數(shù)據。所以，為了通用一些，我們還是要移動結點。

試想，我們先把a結點從鏈表中刪除，然后把a結點插入到b結點的后面，再把b結點刪除，最后把b結點插入到a結點原來的位置。這里的問題是，一旦把a結點從鏈表中刪除，a的原位置就丟失了，所以是無法把b結點插入到a結點原來的位置的。

所以，我們要想辦法記錄a結點的原位置。非常容易想到的辦法是——用指針記錄下a結點的前驅和后繼。于是我寫出了以下代碼：

void swap_wrong(struct list_head *a, struct list_head *b) {struct list_head *prev = a->prev;struct list_head *next = a->next;list_del(a);__list_add(a, b->prev, b);list_del(b);__list_add(b, prev, next); }

乍一看，上面的代碼還挺對的，可是仔細一想，考慮還不周全。經過測試，我發(fā)現(xiàn)上面的代碼只適用于兩個結點不相鄰的情況，一旦a和b相鄰，那么就出錯了——無法正確交換，而且使b結點自己指向自己。

如果考慮相鄰的情況，上面的代碼可以修改為：

void swap(struct list_head *a, struct list_head *b) {struct list_head *prev = a->prev;struct list_head *next = a->next;if(a->next == b){list_del(b);__list_add(b, a->prev, a);}else if(b->next == a){list_del(a);__list_add(a, b->prev, b);}else{list_del(a);__list_add(a, b->prev, b);list_del(b);__list_add(b, prev, next);} }

經過測試，以上代碼沒有問題。但是，這種寫法和第三節(jié)的寫法還是不一樣的，顯然三的寫法更簡潔。

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); }

這種寫法的優(yōu)點是不用分情況討論，不管a和b是否相鄰，都是適用的。

示意圖如下：

3.排序函數(shù)

void bubble_sort(struct list_head *head, int (*compar)(struct list_head *, struct list_head *)) {struct list_head *start = NULL; struct list_head *end = NULL; list_for_each_reverse(end, head) { list_for_each(start, head) { if (start == end) break;if (compar(start, start->next) > 0) {swap(start, start->next); start = start->prev; //start歸位if (start == end) end = end->next; //end歸位 }}} }

第7行：外層循環(huán)，使end結點依次從表尾向首結點取值；
第9行：內層循環(huán)，使start結點依次從首結點向表尾取值；
第11~12行：一旦start和end重合，跳出內層循環(huán)；
第14~16行：從表頭到表尾按照升序排列；
第17~19：這幾行非常重要，也非常容易被忽略。為了強調，我放到下節(jié)說。

4.指針的歸位

在數(shù)組排序中，游標是不需要歸位的，因為我們交換的不是內存地址，而是內存的內容。但是，在本文的鏈表排序中，我們交換的是結點的地址，也就是說結點的位置改變了。

舉例來說，假設當前start指向第3個結點，之后發(fā)生了交換，第3個和第4個交換了，那么隨著交換的發(fā)生，start指向了第4個結點（原來的3變成了現(xiàn)在的4），如果不修正start，繼續(xù)迭代，那么start = start->next，即指向第5個結點，從第3到第5顯然不對，4去哪里了？

所以，發(fā)生交換后，需要把start歸位，之前指向第幾個結點，現(xiàn)在還要指向第幾個。所以有了第17行。

如果start和end交換了，那么還要歸位end，道理同上。于是有了18~19行。

【完】

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。