一、復習數組的選擇排序

選擇排序屬于蠻力法。
首先，掃描整個列表，找到最小的元素，將其和第一個元素交換位置；然后從第二個元素開始掃描列表，找到最小的元素，再將其和第二個元素交換位置……直到從倒數第二個元素開始掃描列表，找到最小的元素，將其和倒數第二個元素交換位置。

假設有4個數，選擇排序的示意圖如下。

二、以Linux內核鏈表為例，進行選擇排序

1. 完整代碼

#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 select_sort(struct list_head *head, int(*cmp)(struct list_head *a, struct list_head *b)) {struct list_head *i, *j, *min;list_for_each(i, head) {if(i == head->prev)break; //當i指向最后一個結點時，排序完成min = i; //用min指向最小的結點j = i->next;list_for_each_from(j, head) {if (cmp(j, min) < 0) {min = j;}}if (min != i) {swap(min, i);i = min; //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);} //尾插，構成鏈表struct data_info *pdata = NULL;list_for_each_entry(pdata, &head, list) {printf("%d ", pdata->data);}printf("\n"); //排序之前select_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 7
1 2 3 4 5 6 7 7 8 9

2. 代碼解析

2.1 swap函數

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

2.2 list_for_each_from宏

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

也就是說，不進行cur的初始化(cur需要在進入for循環之前被初始化)。

2.3 select_sort函數

void select_sort(struct list_head *head, int(*cmp)(struct list_head *a, struct list_head *b)) {struct list_head *i, *j, *min;list_for_each(i, head) {if(i == head->prev)break; //當i指向最后一個結點時，排序完成min = i; //用min指向最小的結點j = i->next;list_for_each_from(j, head) {if (cmp(j, min) < 0) {min = j;}}if (min != i) {swap(min, i);i = min; //i指針歸位}} }

7~9行：i的取值從第一個結點的地址到倒數第二個結點的地址；
第10行：假設i指向最小的結點，用min保存最小的結點的地址；
11~14行：j從i的下一個結點開始遍歷，一直到最后一個結點，這些結點加上i指向的結點，選出其中最小的，其地址由min保存；
17~18行：min和i交換位置，此時，i指向的結點已經在最終位置上；
第19行：由于交換使i改變了位置，所以需要對其歸位。為什么要這樣做，可以參考我的上一篇博文（鏈接已經在上文給出）中的4.4節。

【完】

總結

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

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