链表排序算法（C++）：数组辅助排序、插入排序、归并排序

news/2024/10/15 3:09:20 标签: 排序算法, 链表, c++

文章目录

  • 借助数组排序
  • 插入排序
  • 归并排序
  • 测试用例

数组排序算法参考：冒泡排序、插入排序、选择排序、归并排序、快速排序算法（C++实现）-CSDN博客
链表排序算法参考：链表排序总结（全）（C++）-CSDN博客

这里主要介绍三种链表排序方法，第一种是借助数组进行排序的方法，第二种是插入排序，第三种是归并排序，当然链表排序也可以用快排等其他方法，这里就不一一介绍了。

借助数组排序

顾名思义，就是通过数组来实现间接的链表排序，大概思路就是先将链表里每个节点的值存在数组里，对数组进行排序（数组排序方法有很多种，也可以直接调用sort函数来排序），将排序好的数组再依次赋值给链表的每个节点。
这个排序方法算是一种不那么正统的排序，时间复杂度和空间复杂度会受数组排序算法的影响。如果基于快排，那时间复杂度就是O(nlogn)，空间复杂度最好为O(logn)，最差为O(n)。

/**
 * 数组快排
 */
void quickSort(vector<int> &nums, int begin, int end)
{
    if (begin >= end)
    {
        return;
    }
    int left = begin;
    int right = end;
    int key = begin;

    while (begin < end)
    {
        // 选取了左key，一定要右边先移动
        while (begin < end && nums[end] >= nums[key])
        {
            end--;
        }
        while (begin < end && nums[begin] <= nums[key])
        {
            begin++;
        }
        swap(nums[begin], nums[end]);
    }
    swap(nums[begin], nums[key]);
    key = begin;
    quickSort(nums, left, key - 1);
    quickSort(nums, key + 1, right);
}

/**
 * 借助数组排序（基于快排）
 * 时间复杂度O(nlogn)
 * 空间复杂度跟快排一样：最好为O(logn)，最差为O(n)
 */
void trickSort(listNode *head)
{
    if (head == NULL)
    {
        cout << "link list is empty" << endl;
        return;
    }
    vector<int> nums;
    listNode *p = head;
    while (p != NULL)
    {
        nums.push_back(p->val);
        p = p->next;
    }
    quickSort(nums, 0, nums.size() - 1);
    p = head;
    for (auto num : nums)
    {
        p->val = num;
        p = p->next;
    }
}

插入排序

链表的插入排序和数组的插入排序本质上是一样的，但是实现方法上有些不同
时间复杂度：O(n^2)；空间复杂度：O(1)

/**
 * 链表插入排序
 * 时间复杂度：O(n^2)
 * 空间复杂度：O(1)
 */
void linkInsertSort(listNode **head)
{
    if (*head == NULL || (*head)->next == NULL)
    {
        return;
    }
    // 创建一个哑节点（辅助节点）
    listNode *dummy = new listNode(-1);
    dummy->next = *head;
    listNode *pre = *head;
    listNode *cur = (*head)->next;
    listNode *temp = dummy;
    while (cur != NULL)
    {
        // 如果当前值比上一次插入点的值要小，就只能从头查找插入点,否则，插入点的查找可以从上一个插入点之后开始查找
        if (temp->val > cur->val)
        {
            temp = dummy;
        }

        if (cur->val >= pre->val)
        {
            pre = pre->next;
            cur = cur->next;
        }
        else
        {
            while (temp->next->val < cur->val)
            {
                temp = temp->next;
            }
            pre->next = cur->next;
            cur->next = temp->next;
            temp->next = cur;
            cur = pre->next;
        }
    }
    *head = dummy->next;
}

归并排序

归并排序似乎是链表排序中最常用到的一种排序方法，时间复杂度：O(nlogn)，空间复杂度：O(logn)，由递归决定？也有文章说空间复杂度是O(1)

/**
 * 归并排序
 * 时间复杂度：O(nlogn)
 * 空间复杂度：O(logn)，由递归决定？也有文章说空间复杂度是O(1)
 */
class MergeSort
{
public:
    listNode *merge(listNode *left, listNode *right)
    {
        auto dummy = new listNode(-1);
        auto h = dummy;
        while (left != NULL && right != NULL)
        {
            if (left->val < right->val)
            {
                h->next = left;
                left = left->next;
            }
            else
            {
                h->next = right;
                right = right->next;
            }
            h = h->next;
        }
        h->next = left == NULL ? right : left;
        return dummy->next;
    }

    listNode *mergeSort(listNode *head)
    {
        // 这个是终止条件，一定要有！
        if (head->next == NULL)
            return head;
        listNode *slow = head, *fast = head->next;
        while (fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        auto r_head = slow->next;
        slow->next = NULL;
        auto left = mergeSort(head);
        auto right = mergeSort(r_head);
        return merge(left, right);
    }

    listNode *sortList(listNode *head)
    {
        if (head == NULL || head->next == NULL)
        {
            return head;
        }
        return mergeSort(head);
    }
};

测试用例

#include <iostream>
#include <cstdlib>
#include <random>
#include <algorithm>
#include <vector>

using namespace std;

struct listNode
{
    int val;
    listNode *next;

    // 构造函数
    listNode(int x) : val(x), next(nullptr) {}
};

/**
 * 生成随机数
 */
int randNum(void)
{
    random_device rd;
    int gen(rd());
    return gen % 100;
}

/**
 * 创建单链表
 */
void linkCreate(listNode **head, listNode *p_new)
{
    if (*head == NULL)
    {
        *head = p_new;
        return;
    }
    listNode *p = *head;
    while (p->next != NULL)
    {
        p = p->next;
    }
    p->next = p_new;
    p_new->next = NULL;
}

/**
 * 遍历链表
 */
void linkPrint(listNode *head)
{
    if (head == NULL)
    {
        cout << "link list is empty" << endl;
        return;
    }
    listNode *p = head;
    while (p != NULL)
    {
        cout << p->val << " -> ";
        p = p->next;
    }
    cout << "NULL" << endl;
}

/**
 * 数组快排
 */
void quickSort(vector<int> &nums, int begin, int end)
{
    if (begin >= end)
    {
        return;
    }
    int left = begin;
    int right = end;
    int key = begin;

    while (begin < end)
    {
        // 选取了左key，一定要右边先移动
        while (begin < end && nums[end] >= nums[key])
        {
            end--;
        }
        while (begin < end && nums[begin] <= nums[key])
        {
            begin++;
        }
        swap(nums[begin], nums[end]);
    }
    swap(nums[begin], nums[key]);
    key = begin;
    quickSort(nums, left, key - 1);
    quickSort(nums, key + 1, right);
}

/**
 * 借助数组排序（基于快排）
 * 时间复杂度O(nlogn)
 * 空间复杂度跟快排一样：最好为O(logn)，最差为O(n)
 */
void trickSort(listNode *head)
{
    if (head == NULL)
    {
        cout << "link list is empty" << endl;
        return;
    }
    vector<int> nums;
    listNode *p = head;
    while (p != NULL)
    {
        nums.push_back(p->val);
        p = p->next;
    }
    quickSort(nums, 0, nums.size() - 1);
    p = head;
    for (auto num : nums)
    {
        p->val = num;
        p = p->next;
    }
}

/**
 * 链表插入排序
 * 时间复杂度：O(n^2)
 * 空间复杂度：O(1)
 */
void linkInsertSort(listNode **head)
{
    if (*head == NULL || (*head)->next == NULL)
    {
        return;
    }
    // 创建一个哑节点（辅助节点）
    listNode *dummy = new listNode(-1);
    dummy->next = *head;
    listNode *pre = *head;
    listNode *cur = (*head)->next;
    listNode *temp = dummy;
    while (cur != NULL)
    {
        // 如果当前值比上一次插入点的值要小，就只能从头查找插入点,否则，插入点的查找可以从上一个插入点之后开始查找
        if (temp->val > cur->val)
        {
            temp = dummy;
        }

        if (cur->val >= pre->val)
        {
            pre = pre->next;
            cur = cur->next;
        }
        else
        {
            while (temp->next->val < cur->val)
            {
                temp = temp->next;
            }
            pre->next = cur->next;
            cur->next = temp->next;
            temp->next = cur;
            cur = pre->next;
        }
    }
    *head = dummy->next;
}

/**
 * 归并排序
 * 时间复杂度：O(nlogn)
 * 空间复杂度：O(logn)，由递归决定？也有文章说空间复杂度是O(1)
 */
class MergeSort
{
public:
    listNode *merge(listNode *left, listNode *right)
    {
        auto dummy = new listNode(-1);
        auto h = dummy;
        while (left != NULL && right != NULL)
        {
            if (left->val < right->val)
            {
                h->next = left;
                left = left->next;
            }
            else
            {
                h->next = right;
                right = right->next;
            }
            h = h->next;
        }
        h->next = left == NULL ? right : left;
        return dummy->next;
    }

    listNode *mergeSort(listNode *head)
    {
        // 这个是终止条件，一定要有！
        if (head->next == NULL)
            return head;
        listNode *slow = head, *fast = head->next;
        while (fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        auto r_head = slow->next;
        slow->next = NULL;
        auto left = mergeSort(head);
        auto right = mergeSort(r_head);
        return merge(left, right);
    }

    listNode *sortList(listNode *head)
    {
        if (head == NULL || head->next == NULL)
        {
            return head;
        }
        return mergeSort(head);
    }
};

int main(int argc, char const *argv[])
{
    listNode *head = NULL, *p_new = NULL;
    MergeSort mergeTool;
    // 创建链表
    for (int i = 0; i < 10; i++)
    {
        p_new = (listNode *)malloc(sizeof(listNode));
        p_new->val = randNum();
        linkCreate(&head, p_new);
    }
    // 遍历链表
    linkPrint(head);
    head = mergeTool.sortList(head);
    linkPrint(head);

    return 0;
}

http://www.niftyadmin.cn/n/5705440.html

相关文章

YOLOv11改进策略【Conv和Transformer】| ACmix 卷积和自注意力的结合，充分发挥两者优势

YOLOv11改进策略【Conv和Transformer】| ACmix 卷积和自注意力的结合，充分发挥两者优势

一、本文介绍 本文记录的是利用ACmix改进YOLOv11检测模型，卷积和自注意力是两种强大的表示学习技术，本文利用两者之间潜在的紧密关系，进行二次创新，实现优势互补，减少冗余，通过实验证明，实现模型有效涨点。 专栏目录：YOLOv11改进目录一览 | 涉及卷积层、轻量化、注意力…
阅读更多...
SharedPreferences的使用场景和限制

SharedPreferences的使用场景和限制

SharedPreferences是Android平台上一种轻量级的数据存储方式&#xff0c;它主要用于存储少量的键值对数据&#xff0c;这些数据通常用于保存应用程序的配置信息或用户偏好设置。以下是关于SharedPreferences的使用场景和限制的详细分析。 一、SharedPreferences的使用场景 1.…
阅读更多...
JavaEE: 深入解析HTTP协议的奥秘(1)

JavaEE: 深入解析HTTP协议的奥秘(1)

文章目录 HTTPHTTP 是什么HTTP 协议抓包fiddle 用法 HTTP 请求响应基本格式 HTTP HTTP 是什么 HTTP 全称为"超文本传输协议". HTTP不仅仅能传输文本,还能传输图片,传输音频文件,传输其他的各种数据. 因此它广泛应用在日常开发的各种场景中. HTTP 往往是基于传输层的…
阅读更多...
Matlab中实现数据共享

Matlab中实现数据共享

背景描述: 自定义了一个类&#xff0c;在类方法中需要缓存数据&#xff0c;以供其他方法或者实例共享数据&#xff0c;但是类的属性properties没有Static特性 解决方案: 方法一: 把需要共享的数据封装在一个单独的类里 % SharedData.m classdef SharedData < handle % 注…
阅读更多...
Qt实现侧边栏功能

Qt实现侧边栏功能

本文介绍Qt实现侧边栏功能。 采用Qt进行界面应用程序开发时&#xff0c;经常遇到侧边栏功能实现&#xff0c;采用侧边栏可以将一些暂时不用到的功能隐藏&#xff0c;使用的时候点击一下相应的按钮即可弹出&#xff08;动画方式&#xff09;功能菜单。减少主界面控件数量&#…
阅读更多...
vue3中如何给响应式对象

vue3中如何给响应式对象

reactive定义响应式对象&#xff1a; 首先我们定义一个reactive响应式对象 <template><div class"Car"><h2>汽车名称: {{ car.brand }}</h2><p>价格&#xff1a;{{ car.price }}</p><button click"changeName"&g…
阅读更多...
Taro 中 echarts 图表使用

Taro 中 echarts 图表使用

1 下载 echarts4taro3 yarn add echarts4taro3 或 pnpm add echarts4taro3 或 npm i echarts4taro3 --save2 图表初始化需要先加载echarts模块 import * as echarts from "echarts4taro3/lib/assets/echarts"; // 这里用了内置的&#xff0c;也可以用自定义的 echa…
阅读更多...
Unix System Overview

Unix System Overview

Unix体系结构 Unix由内核、系统调用、shell外壳、库函数以及应用程序五部分组成 内核居于最中心&#xff0c;是整个Unix结构的核心&#xff0c;向上为应用进程提供系统服务&#xff0c;向下管理硬件资源 系统调用是内核提供给外部请求系统服务的入口&#xff0c;位于内核边界&…
阅读更多...
最新文章

Copyright @ 2022~2023