1. 全栈程序员必看首页

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

全栈程序员-用户IM • • 未分类

数据结构–链表的排序详解1、前言前面两篇博客，我已经把线性表的两种基本的表示形式，做了一个基本的介绍和一些对比。但是，我突然发现在链表这里我缺少一个很重要的内容，那就是对我们的链表进行排序，其实，在连接两个链表的时候，就要求我们的那两个链表是有序的。2、链表排序—最简单、直接的方式（直接采用冒泡或者选择排序，而且不是交换结点，只交换数据域）//线性表的排序,采用冒泡排序,直接遍历链表voidListsort(Nod

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

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、先我们通过采取增大数据量的方式，比较两种排序在效率如何

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

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

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

//参数为头结点和需要交换的两个结点的位置（起点为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
输出结果：
这里写图片描述

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/183051.html原文链接：https://javaforall.cn

【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛

【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

赞 (0)
全栈程序员-用户IM全栈程序员-用户IM
0 0


相关推荐

  • <span>查找可用的谷歌IP地址</span>

    查找可用的谷歌IP地址

    查找可用的谷歌IP地址

    全栈程序员-用户IM 全栈程序员-用户IM
    2021年11月14日
  • 免费使用谷歌云服务器一年多少钱_谷歌云服务器永久免费

    免费使用谷歌云服务器一年多少钱_谷歌云服务器永久免费

    免费使用谷歌云服务器一年多少钱_谷歌云服务器永久免费上周自己撸了一年的谷歌云服务器，昨天也帮同事搞了一发。毕竟工作中还是少不了向西方取经。把自己的经验总结一下吧，方便后来之人。说一下前提条件：1.持有外币卡，例有VISA标识、万事达标识、JCB标识的信用卡2.可以上谷歌且有谷歌账号，没有的话自己注册一个。免费申请链接在这：https://cloud.google.com/free/进入申请界面后有一个国家/地区的选项，截止目前没有找到中国的，直接选择了美国即可账户类型选择个人，然后地址直接百度一下美国地址生成器然后找到对应的网站，复制粘贴

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年10月5日
  • 将十进制小数转化为二进制小数

    将十进制小数转化为二进制小数

    将十进制小数转化为二进制小数小数表示原理你了解小数的表示原理吗？我的十进制小数换成二进制该如何表示？比如：0.3的二进制表示为：0.0100110011001….(小数乘以2，取整，小数部分继续乘以2，取整，得到小数部分0为止，将整数顺序排列。0.8125×2=1.625取整1,小数部分是0.6250.625×2=1.25取整1,小数部分是0.250.25×2=0.5取整0,小

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年9月24日
  • 梯度下降法和随机梯度下降法的区别_梯度下降法的优缺点

    梯度下降法和随机梯度下降法的区别_梯度下降法的优缺点

    梯度下降法和随机梯度下降法的区别_梯度下降法的优缺点1.梯度　　在微积分里面，对多元函数的参数求∂偏导数，把求得的各个参数的偏导数以向量的形式写出来，就是梯度。比如函数f(x,y),分别对x,y求偏导数，求得的梯度向量就是(∂f/∂x,∂f/∂y)T,简称gradf(x,y)或者▽f(x,y)。对于在点(x0,y0)的具体梯度向量就是(∂f/∂x0,∂f/∂y0)T.或者▽f(x0,y0)，如果是3个参数的向量梯度，就是(∂f/∂x,…

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年9月10日
  • Godot 2D 和 3D 游戏引擎[通俗易懂]

    Godot 2D 和 3D 游戏引擎[通俗易懂]

    Godot 2D 和 3D 游戏引擎[通俗易懂]Godot是一个全新开发的游戏引擎，其功能集类似知名的跨平台游戏引擎Unity，可用于开发PC、主机、移动和Web游戏。开发者引擎的2D和动画支持要强于Unity，表示在功能和特性上没有其它开源游戏引擎能相媲美。Godot引擎内置了类似Unity的编辑器，GUI工具包，2D/3D物理支持，支持OpenGLES2.0功能集的3D渲染器，易于学习的语言和API，支持用ASM.js或GoogleNativeClient输出HTML5代码，支持Linux、Windows和OSX开发平台…

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年5月25日
  • 小波变换原理_小波变换的缺点

    小波变换原理_小波变换的缺点

    小波变换原理_小波变换的缺点https://www.cnblogs.com/warmbeast/p/7809286.html从傅里叶变换到小波变换，并不是一个完全抽象的东西，可以讲得很形象。小波变换有着明确的物理意义，如果我们从它的提出时所面对的问题看起，可以整理出非常清晰的思路。下面就按照傅里叶–>短时傅里叶变换–>小波变换的顺序，讲一下为什么会出现小波这个东西、小波究竟是怎样的思路。傅里叶变换关于傅…

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年10月30日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号