一、复习数组的选择排序

选择排序属于蛮力法。
首先，扫描整个列表，找到最小的元素，将其和第一个元素交换位置；然后从第二个元素开始扫描列表，找到最小的元素，再将其和第二个元素交换位置……直到从倒数第二个元素开始扫描列表，找到最小的元素，将其和倒数第二个元素交换位置。

假设有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节。

【完】

总结

以上是生活随笔为你收集整理的双向循环链表的选择排序的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。