学习笔记-数据结构-线性表（2024-04-18）- 单向链表选择排序 - wpsshop博客
devbox
笔触狂放9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

学习笔记-数据结构-线性表（2024-04-18）- 单向链表选择排序

作者：笔触狂放9 | 2024-04-24 12:53:32

赞

踩

学习笔记-数据结构-线性表（2024-04-18）- 单向链表选择排序

试以单向链表为存储结构实现简单选择排序的算法。

实现递增排序，首先选择一个元素作为第一个比较值，遍历其他所有的元素，如果发现其他元素中有比它小的元素，则交换两个元素，这样每一趟都能找到符合要求的最小值

正经的单向链表排序，不是换数据的那种！
思想是选择排序的思想，但问题在于单链表结构不同于数组的直接交换，需要断链和重新成链等各种操作，稍不留神就直接G了

具体实现步骤如下：

  • 初始化指针变量a和b，它们都指向链表的头节点。
  • 外层循环遍历链表，直到节点b是链表中的最后一个节点。
  • 内层循环遍历以节点b为起始的子链表，寻找其中最小的节点d。
  • 如果节点b的值大于节点d的值，说明需要将节点d插入到节点b之前。
  • 根据不同情况进行节点的移动和连接操作：
    • 如果节点d紧跟在节点b后面，分为两种情况：
      • 如果节点b是链表的头节点，则直接将节点d移动到节点b之前，并调整头节点的指针。
      • 如果节点b不是链表的头节点，则将节点d移动到节点b之前，并更新a的next指针。
    • 如果节点b和节点d之间有其他节点，也分为两种情况：
      • 如果节点b是链表的头节点，则将节点d移动到节点b之前，并更新头节点的指针。
      • 如果节点b不是链表的头节点，则将节点d移动到节点b之前，并更新a的next指针。
  • 完成内层循环后，更新a和b的指针，继续下一轮循环，直到整个链表都被排序完成。
  • 最后返回排序后的链表头节点。

下面是C语言写法：

typedef struct Node
{
    int data;
    struct Node *next;
}LinkNode;


LinkNode* selectionSort(LinkNode* head) 
{ 
    LinkNode *a, *b, *c, *d, *r; // 声明指针变量 a, b, c, d, r

    a = b = head; // 初始化指针变量 a, b，它们指向链表头部

    // 当 b 不是最后一个节点时执行循环
    while (b->next) { 

        c = d = b->next; // 初始化指针变量 c, d，它们指向 b 的下一个节点

        // 当 d 指向一个有效节点时执行循环
        while (d) { 

            if (b->data > d->data) { // 如果 b 的值大于 d 的值

                if (b->next == d) { // 如果 d 紧跟在 b 后面

                    if (b == head) { // 如果 b 是链表的头节点

                        // 将 d 移动到 b 的前面
                        b->next = d->next; 
                        d->next = b; 

                        // 交换 b 和 d 的指针
                        r = b; 
                        b = d; 
                        d = r; 

                        c = d; // 更新 c

                        // 更新链表头部
                        head = b; 

                        // 跳到下一个元素，因为它已经是有序的
                        d = d->next; 
                    } 
                    else { // 如果 b 不是链表的头节点

                        // 将 d 移动到 b 的前面
                        b->next = d->next; 
                        d->next = b; 
                        a->next = d; 

                        // 交换 b 和 d 的指针
                        r = b; 
                        b = d; 
                        d = r; 

                        c = d; // 更新 c

                        // 跳到下一个元素，因为它已经是有序的
                        d = d->next; 
                    } 
                } 
                else { // 如果 b 和 d 之间有一些非零节点

                    if (b == head) { // 如果 b 是链表的头节点

                        // 交换 b->next 和 d->next
                        r = b->next; 
                        b->next = d->next; 
                        d->next = r; 
                        c->next = b; 

                        // 交换 b 和 d 的指针
                        r = b; 
                        b = d; 
                        d = r; 

                        c = d; // 更新 c

                        // 跳到下一个元素，因为它已经是有序的
                        d = d->next; 

                        // 更新链表头部
                        head = b; 
                    } 
                    else { // 如果 b 不是链表的头节点

                        // 交换 b->next 和 d->next
                        r = b->next; 
                        b->next = d->next; 
                        d->next = r; 
                        c->next = b; 
                        a->next = d; 

                        // 交换 b 和 d 的指针
                        r = b; 
                        b = d; 
                        d = r; 

                        c = d; // 更新 c

                        // 跳到下一个元素，因为它已经是有序的
                        d = d->next; 
                    } 
                } 
            } 
            else { // 如果 b 的值不大于 d 的值

                // 更新 c 并跳到下一个元素，因为它已经是有序的
                c = d; 
                d = d->next; 
            } 
        } 

        a = b; // 更新 a
        b = b->next; // 更新 b
    } 

    return head; // 返回排序后的链表头部
} 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120

下面是Java语言写法：


public class Main {
  
    public static class Node {
        int data; 
        Node next; 
    };

    public static Node selectionSort(Node head)
    {
        Node a, b, c, d, r;
        a = b = head;
        while (b.next != null) {
            c = d = b.next;
            while (d != null) {
                if (b.data > d.data) {
                    if (b.next == d) {
                        if (b == head) {
                            b.next = d.next;
                            d.next = b;
                            r = b;
                            b = d;
                            d = r;
                            c = d;
                            head = b;
                            d = d.next;
                        }
                        else {
                            b.next = d.next;
                            d.next = b;
                            a.next = d;
                            r = b;
                            b = d;
                            d = r;
                            c = d;
                            d = d.next;
                        }
                    }
                    else {
                        if (b == head) {
                            r = b.next;
                            b.next = d.next;
                            d.next = r;
                            c.next = b;
                            r = b;
                            b = d;
                            d = r;
                            c = d;
                            d = d.next;
                            head = b;
                        }
                        else {
                            r = b.next;
                            b.next = d.next;
                            d.next = r;
                            c.next = b;
                            a.next = d;
                            r = b;
                            b = d;
                            d = r;
                            c = d;
                            d = d.next;
                        }
                    }
                }
                else {
                    c = d;
                    d = d.next;
                }
            }
            a = b;
            b = b.next;
        }
        return head;
    }

	// 新建Node节点
    static Node newNode(int val)
    { 
        Node temp = new Node(); 
  
        temp.data = val; 
  
        temp.next = null; 
  
        return temp; 
    } 
} 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88

示例

以 -2-0-0-3-5-1- 单链表为例
由于动态演示图较大，csdn无法上传，请移步至 https://gitee.com/xjk2000/image-storage/blob/master/1.gif
Java代码测试执行：
测试代码
执行结果：
在这里插入图片描述

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/479385
推荐阅读
相关标签