数据结构--链表的排序详解

喜欢ヅ旅行 2022-07-16 13:15 160阅读 0赞

**1、前言**  
前面两篇博客，我已经把线性表的两种基本的表示形式，做了一个基本的介绍和一些对比。但是，我突然发现在链表这里我缺少一个很重要的内容，那就是对我们的链表进行排序，其实，在连接两个链表的时候，就要求我们的那两个链表是有序的。

**2、链表排序—最简单、直接的方式（直接采用冒泡或者选择排序，而且不是交换结点，只交换数据域）**

//线性表的排序,采用冒泡排序,直接遍历链表
    void Listsort(Node* & head) {
        int i = 0;
        int j = 0;
        //用于变量链表
        Node * L = head;
        //作为一个临时量
        Node * p;
        Node * p1;
        //如果链表为空直接返回
        if (head->value == 0)return;
    
        for (i = 0; i < head->value - 1; i++) {
            L = head->next;
            for (j = 0; j < head->value - i - 1; j++) {
                //得到两个值
                p = L;
                p1 = L->next;
                //如果前面的那个比后面的那个大，就交换它们之间的是数据域
                if (p->value > p1->value) {
                    Elemtype temp = p->value;
                    p->value = p1->value;
                    p1->value = temp;
                }
                L = L->next;
            }
        }
    }

因为排序中速度比较快的如快速排序是要求它们的数据域的地址是相连接的，它比较适合于顺序结构，而链式结构的时候，我们就只有使用只会进行前后两个比较多排序算法，比如冒泡排序等。我们这里是没有交换结点的一种排序方式，这种方式简单，明了，这样就是数组排序的时候是一样的。后面我会写通过交换结点的方式的排序。  
下面我们就讨论讨论这个排序算法的时间复杂度了，因为它是使用冒泡排序的，它的时间只要消耗在那两重循环，所以时间复杂度为：O(n\*n),这个效率实在是太低，下面我们对这个想(ˇˍˇ) 想～通过另外一种方式来实现链表的排序

**3、另外一种链表排序方式**  
我们在讨论排序算法的时候，都是把数据存放在数组中进行讨论的，在顺序结构下，我们可以采取很多高效的排序算法，那么这个就是我们另外一种对链表排序的方式，先把链表的内容存放到数组中（时间为O(n)），然后，我们在对那个数组进行排序（最快为nlog(n)），最后，存放链表中（时间为O(n)）。通过计算，我们可以得到它的时间复杂为（O(nlogn)）,这个速度已经和顺序结构下差不多了，可以接受

void Listsort_1(Node* & head) {
        int i = 0;
        int j = 0;
        //用于变量链表
        Node * L = head;
        //如果链表为空直接返回
        if (head->value == 0)return;
        Elemtype * copy = new Elemtype[head->value];
        //变量链表，存放数组
        for (i = 0; i < head->value; i++) {
            L = L->next;
            copy[i] = L->value;
        }
        //调用STL中的sort函数
        sort(copy, copy + head->value);
        L = head;
        //存放回链表中
        for (i = 0; i < head->value; i++) {
            L = L->next;
              L->value= copy[i];
        }
    }

**4、先我们通过采取增大数据量的方式，比较两种排序在效率如何**

![这里写图片描述][20161118201120262]  
如图所示，在数据量为10000的时候，明显第二种排序算法消耗的时间比第一种快了28倍左右。

**5、下面通过交换结点实现链表的排序**  
首先我们编写交换结点的函数，结点的交换主要就是考虑结点的指针域的问题，其中相邻两个结点是一种特殊的情况，要拿出来特别考虑。我们先画出结点交换的思路图，如下图  
首先我们给出相邻两个结点交换的思路：  
![这里写图片描述][20161118211100945]

下面是普通情况下的交换如下图  
![这里写图片描述][20161118211901508]

//参数为头结点和需要交换的两个结点的位置（起点为1）
    void swap_node(Node * & head,int i,int j) {
        //位置不合法
        if (i<1 || j<1 || i>head->value || j >head->value) {
            cout << "请检查位置是否合法" << endl;
            return;
        }
        //同一个位置不用交换
        if (i == j)
        {
            return;
        }
        //相邻两个交换比较简单
        if (abs(i - j) == 1) {
            //位置靠前的那个结点的前一个结点
            Node * pre;
            if (i < j)
                pre = getitem(head, i);
            else
                pre = getitem(head, j);
    
            //保存第一个结点
            Node * a = pre->next;
            //保存第二结点
            Node * b = a->next;
            //改变pre下一个结点的值
            pre->next = b;
            //必须先把b的下一个结点值给a先
            a->next = b->next;
            //让b的下一个结点等于a
            b->next = a;
            return;
        }
    
        //第一个结点前一个结点
        Node * a = getitem(head, i);
        //第二个结点的前一个结点
        Node * b = getitem(head, j);
        //第一个结点
        Node * p = a->next;
        //第二个结点
        Node * q = b->next;
        //第一个结点的下一个结点
        Node * p_next = p->next;
        //第二结点的下一个结点
        Node * q_next = q->next;
    
        //a的下一个结点指向第二个结点q
        a->next = q;
        //第二结点的下一个结点指向第一个结点的下一个结点
        q->next = p_next;
        //b的下一个结点指向第一个结点p
        b->next = p;
        //第一个结点的下一个结点指向第二个结点的下一个结点
        p->next = q_next;
    
    }

排序时候的代码，切记交换结点都是前后结点交换，所以交换完成后，L就已经被移动到下一个结点了，故不要再执行：L=L->next

//线性表的排序，交换结点
    void Listsort_Node(Node* & head) {
        int i = 0;
        int j = 0;
        //用于变量链表
        Node * L = head;
        //作为一个临时量
        Node * p;
        Node * p1;
        //如果链表为空直接返回
        if (head->value == 0)return;
        int flag = 0;
        cout << head->value << endl;
        for (i = 0; i < head->value - 1; i++) {
            L = head->next;
            for (j = 0; j < head->value - 1 - i; j++) {
                //如果我们交换了结点，那么我们就已经在交换结点的时候，把L移动到下一个结点了，所以不要
                //再执行：L = L->next;，否则会报错的
                if (L->value > L->next->value) {
                    flag = 1;
                    swap_node(head, j + 1, j + 2);
    
                }
                if (flag == 1) {
                    flag = 0;
                }
                else {
                    L = L->next;
                }
    
            }   
        }
    }

好了，今天的就写到这里了，今天通过写交换结点，发现链表真的很容易忽悠人，我就被忽悠了一个小时，才知道那个结点已经被移动到下一个结点了。

**最后，补充一个实现链表反转的好方法（感觉你在头文件里面计算一下链表的长度可以带来很多遍历的）**

void rollback(Node * & head) {
        //先知道了最后一个元素和第一个元素的位置
        int end = head->value;
        int start = 1;
        //两边同时开工
        //进行调换
        while (1) {
            if (end == start)
                return;
            swap_node(head, end, start);
            --end;
            ++start;
        }
    }

希望大家，对我写的代码做出一些评价。我想想还是直接贴个完成的代码出来好了，调转代码也在里面了

#include<iostream>
    #include<ctime>
    #include<cstdlib>
    #include<windows.h>
    #include<algorithm>
    using namespace std;
    typedef int Elemtype;
    
    //链式结构，我们打算在链表中添加一个
    //保存长度的头结点，加入这个结点可以方便我们对结点做一些
    //基本的操作，结点保存的是线性表的长度
    struct Node
    {
        //结点的值,如果是头结点，保存是链表的长度
        Elemtype value;
        //下一个结点的地址
        Node * next;
    
    };
    
    //创建一个空链表，每个头结点就代表一个链表
    void InitList(Node * & head) {
        head = new Node();
        head->value = 0;
        head->next = NULL;
    }
    //销毁一个链表
    void DestroyList(Node * & head) {
        delete head;
        head = NULL;
    }
    
    //清空整个列表
    void ClearList(Node * & head) {
        head->value = 0;
        head->next = NULL;
    }
    
    //插入函数
    bool Listinsert(Node * & head, int i, Elemtype value) {
    
        //插入到前面的方法
        int j = 0;
        Node * L = head;
        //如果插入的位置不合法，直接返回错误提示
        if (i<1 || i>head->value + 1)return false;
    
        //得到插入位置的前一个结点
        while (j < i - 1) {
            L = L->next;
            ++j;
        }
    
        //s是一个临时结点
        Node * s = new Node();
        s->value = value;    //先对临时结点赋值
        s->next = L->next;   //让临时结点下一个位置指向当前需要插入前一个结点的下一个位置
        L->next = s;          //让前一个结点下一个位置指向临时结点，完成
                              //线性表的长度加一
        ++head->value;
        return true;
    }
    //得到某个位置上的值
    Node * getitem(Node * & head, int i) {
        //我们要求程序返回特定位置上的值
        //我们一样是从头结点开始寻找该位置
        int j = 0;
        Node * L = head;
        //想要的那个位置是否合法
        if (i<1 || i >head->value)return NULL;
    
        //同样是先得到前一个结点
        while (j < i - 1) {
            L = L->next;
            ++j;
        }
        //value = L->next->value;
        return L;
    }
    //线性表的排序,采用冒泡排序,直接遍历链表
    void Listsort(Node* & head) {
        int i = 0;
        int j = 0;
        //用于变量链表
        Node * L = head;
        //作为一个临时量
        Node * p;
        Node * p1;
        //如果链表为空直接返回
        if (head->value == 0)return;
    
        for (i = 0; i < head->value - 1; i++) {
            L = head->next;
            for (j = 0; j < head->value - i - 1; j++) {
                //得到两个值
                p = L;
                p1 = L->next;
                //如果前面的那个比后面的那个大，就交换它们之间的是数据域
                if (p->value > p1->value) {
                    Elemtype temp = p->value;
                    p->value = p1->value;
                    p1->value = temp;
                }
                L = L->next;
            }
        }
    }
    //通过数组来完成我的排序
    void Listsort_by_array(Node* & head) {
        int i = 0;
        int j = 0;
        //用于变量链表
        Node * L = head;
        //如果链表为空直接返回
        if (head->value == 0)return;
        Elemtype * copy = new Elemtype[head->value];
        //变量链表，存放数组
        for (i = 0; i < head->value; i++) {
            L = L->next;
            copy[i] = L->value;
        }
        //调用STL中的sort函数
        sort(copy, copy + head->value);
        L = head;
        //存放回链表中
        for (i = 0; i < head->value; i++) {
            L = L->next;
            L->value = copy[i];
        }
    }
    
    //参数为头结点和需要交换的两个结点的位置（起点为1）
    void swap_node(Node * & head,int i,int j) {
        //位置不合法
        if (i<1 || j<1 || i>head->value || j >head->value) {
            cout << "请检查位置是否合法" << endl;
            return;
        }
        //同一个位置不用交换
        if (i == j)
        {
            return;
        }
        //相邻两个交换比较简单
        if (abs(i - j) == 1) {
            //位置靠前的那个结点的前一个结点
            Node * pre;
            if (i < j)
                pre = getitem(head, i);
            else
                pre = getitem(head, j);
    
            //保存第一个结点
            Node * a = pre->next;
            //保存第二结点
            Node * b = a->next;
            //改变pre下一个结点的值
            pre->next = b;
            //必须先把b的下一个结点值给a先
            a->next = b->next;
            //让b的下一个结点等于a
            b->next = a;
            return;
        }
    
        //第一个结点前一个结点
        Node * a = getitem(head, i);
        //第二个结点的前一个结点
        Node * b = getitem(head, j);
        //第一个结点
        Node * p = a->next;
        //第二个结点
        Node * q = b->next;
        //第一个结点的下一个结点
        Node * p_next = p->next;
        //第二结点的下一个结点
        Node * q_next = q->next;
    
        //a的下一个结点指向第二个结点q
        a->next = q;
        //第二结点的下一个结点指向第一个结点的下一个结点
        q->next = p_next;
        //b的下一个结点指向第一个结点p
        b->next = p;
        //第一个结点的下一个结点指向第二个结点的下一个结点
        p->next = q_next;
    
    }
    //反转
    void rollback(Node * & head) {
        //先知道了最后一个元素和第一个元素的位置
        int end = head->value;
        int start = 1;
        //两边同时开工
        //进行调换
        while (1) {
            if (end <= start)
                return;
            swap_node(head, end, start);
            --end;
            ++start;
        }
    }
    void print(Node * & head);
    //线性表的排序,采用冒泡排序,直接遍历链表
    //线性表的排序，交换结点
    void Listsort_node(Node* & head) {
        int i = 0;
        int j = 0;
        //用于变量链表
        Node * L = head;
        //作为一个临时量
        Node * p;
        Node * p1;
        //如果链表为空直接返回
        if (head->value == 0)return;
        int flag = 0;
    
        for (i = 0; i < head->value - 1; i++) {
            L = head->next;
            for (j = 0; j < head->value - 1 - i; j++) {
                //如果我们交换了结点，那么我们就已经在交换结点的时候，把L移动到下一个结点了，所以不要
                //再执行：L = L->next;，否则会报错的
                if (L->value > L->next->value) {
                    flag = 1;
                    swap_node(head, j + 1, j + 2);
    
                }
                if (flag == 1) {
                    flag = 0;
                }
                else {
                    L = L->next;
                }
    
            }   
        }
    }
    
    void print(Node * & head) {
        //输出我们只需要传入头结点，然后循环判断当前结点下一个结点是否为空，
        //这样就可以输出所有内容
        Node * L = head;
        while (L->next) {
            L = L->next;
            cout << L->value << " ";
        }
        cout << endl;
    }
    int main() {
        //链表的头结点，不存放任何值，首先初始化头结点
        Node * head;
    
        Node * head_array;
        Node * head_node;
        Node * head_roll;
        srand((int)time(NULL));     //每次执行种子不同，生成不同的随机数
        //创建一个链表
    
        InitList(head); 
        InitList(head_array);
        InitList(head_node);
        InitList(head_roll);
    
        int i;
        cout << "请输入需要插入元素个数" << endl;
        int n;
        cin >> n;//5
        //cout << "请输入" << n << "个值" << endl;
        for (i = 0; i < n; i++) {
            Elemtype temp;
            temp = rand();
            if (!Listinsert(head, i + 1, temp)) {
                cout << "插入元素失败" << endl;
            }
            if (!Listinsert(head_array, i + 1, temp)) {
                cout << "插入元素失败" << endl;
            }
            if (!Listinsert(head_node, i + 1, temp)) {
                cout << "插入元素失败" << endl;
            }
            if (!Listinsert(head_roll, i + 1, temp)) {
                cout << "插入元素失败" << endl;
            }
    
        }
        cout << "初始化结果" << endl;
        print(head);
        cout << "反转结果" << endl;
        rollback(head_roll);
        print(head_roll);
        cout << "冒泡排序（数据域交换）" << endl;
        Listsort(head);
        print(head);
        cout << "借数组为媒介进行排序（数据域交换）" << endl;
        Listsort_by_array(head_array);
        print(head_array);
        cout << "冒泡排序（结点交换）" << endl;
        Listsort_node(head_node);
        print(head_node);
        system("pause");
        return 0;
    
    }

运行环境：vs2015  
输出结果：  
![这里写图片描述][20161118224625017]

[20161118201120262]: /images/20220715/1cfe59d069874c1db6c8bdfdb11a8b56.png
[20161118211100945]: /images/20220715/4709a82dfe514f3caac9d64a1154fb39.png
[20161118211901508]: /images/20220715/c4544ff70bfb49c3843acda582d3ea34.png
[20161118224625017]: /images/20220715/c819bed5b7b74b49b89b3a6eeb4aa676.png