双向循环链表的选择排序

比眉伴天荒 2022-06-04 01:39 180阅读 0赞

# 一、复习数组的选择排序 #

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

假设有4个数，选择排序的示意图如下。

![这里写图片描述][SouthEast]

# 二、以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][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`节。

【完】

[SouthEast]: /images/20220604/6074b58ae8464441aa6a267314d142cc.png
[http_blog.csdn.net_longintchar_article_details_78638975]: http://blog.csdn.net/longintchar/article/details/78638975