归并排序 Listnode* vector＜int＞ vector＜ListNode*＞

news/2025/2/25 13:32:32

加粗样式

ListNode* merge(ListNode* l1,ListNode* l2){
        ListNode* dummyhead=new ListNode(0);
        ListNode* cur=dummyhead;

        while(l1&&l2){
            if(l1->val>=l2->val){
                cur->next=l2;
                l2=l2->next;
                cur=cur->next;
            }
            else if(l1->val<l2->val){
                cur->next=l1;
                l1=l1->next;
                cur=cur->next;
            }
        }
        if(l1){
            cur->next=l1;
        }
        if(l2){
            cur->next=l2;
        }
        return dummyhead->next;
    }

    ListNode* fidmid(ListNode* head){
        ListNode* slow=head;
        ListNode* fast=head->next;
        while(fast&&fast->next){
            slow =slow->next;
            fast=fast->next->next;
        }
        return slow;
    }

    ListNode* sortList(ListNode* head) {
        if(!head||!head->next) return head;
        ListNode* mid = fidmid(head);
        ListNode* right1 = mid->next;
        mid->next = nullptr;
        ListNode* left=sortList(head);
        ListNode* right=sortList(right1);
        return merge(left,right);
   }

vector<ListNode*> 的归并排序（Merge Sort for Linked List Vector）

归并排序适用于链表，因为链表不支持随机访问，而归并排序的 合并（Merge）操作 仅使用 指针操作，无需额外存储，且时间复杂度为 O(N log K)（N 是总节点数，K 是链表个数）。

归并思路

  1. 使用分治法（Divide & Conquer）：
    • 递归地将 vector<ListNode*> 分成两半，直到 vector 只剩一个链表。
  2. 合并两个链表：
    • 使用 mergeTwoLists() 合并两个有序链表。

C++ 实现

#include <iostream>
#include <vector>
using namespace std;

// 定义链表节点
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    // 合并两个有序链表
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (!l1) return l2;
        if (!l2) return l1;

        if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }

    // 归并排序合并 K 个链表
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return nullptr;
        return mergeKListsHelper(lists, 0, lists.size() - 1);
    }

private:
    // 递归合并 `lists[left]` 到 `lists[right]`
    ListNode* mergeKListsHelper(vector<ListNode*>& lists, int left, int right) {
        if (left == right) return lists[left];  // 只有一个链表，直接返回
        if (left > right) return nullptr;       // 无效区间，返回空

        int mid = left + (right - left) / 2;    // 计算中点
        ListNode* l1 = mergeKListsHelper(lists, left, mid);
        ListNode* l2 = mergeKListsHelper(lists, mid + 1, right);

        return mergeTwoLists(l1, l2);  // 合并左右两个部分
    }
};

// 测试代码
void printList(ListNode* head) {
    while (head) {
        cout << head->val << " -> ";
        head = head->next;
    }
    cout << "NULL" << endl;
}

int main() {
    // 创建多个升序链表
    ListNode* list1 = new ListNode(1);
    list1->next = new ListNode(4);
    list1->next->next = new ListNode(7);

    ListNode* list2 = new ListNode(2);
    list2->next = new ListNode(5);
    list2->next->next = new ListNode(8);

    ListNode* list3 = new ListNode(3);
    list3->next = new ListNode(6);
    list3->next->next = new ListNode(9);

    vector<ListNode*> lists = {list1, list2, list3};

    Solution solution;
    ListNode* mergedList = solution.mergeKLists(lists);

    cout << "合并后的链表: ";
    printList(mergedList);

    return 0;
}

代码解析

1️⃣ mergeTwoLists()

  • 递归合并两个 有序链表，返回合并后的头节点。
  • 时间复杂度 O(N)。

2️⃣ mergeKListsHelper()

  • 递归分治 vector<ListNode*>：
    • 递归终止条件：当 left == right 时，返回 lists[left]。
    • 分割：将 lists 分为两部分，递归调用 mergeKListsHelper() 处理。
    • 合并：使用 mergeTwoLists() 合并两个部分。
  • 时间复杂度 O(N log K)。

3️⃣ mergeKLists()

  • 入口函数，调用 mergeKListsHelper() 处理 lists[0] ~ lists[K-1]。

时间 & 空间复杂度分析

操作时间复杂度
合并两个链表O(N)
递归深度（log K 轮）O(log K)
总时间复杂度O(N log K)
  • K 是链表个数，N 是所有节点数。
  • log K 轮，每轮 O(N) 操作，总复杂度 O(N log K)。

空间复杂度： O(log K)（递归栈）。

示例运行

输入

list1: 1 -> 4 -> 7 -> NULL
list2: 2 -> 5 -> 8 -> NULL
list3: 3 -> 6 -> 9 -> NULL

输出

合并后的链表: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> NULL

其他方法

🔹 方法 1：优先队列（最小堆）

利用 priority_queue 维护 K 个链表的头节点，弹出最小值插入结果链表。

ListNode* mergeKLists(vector<ListNode*>& lists) {
    auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
    priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);

    for (auto node : lists) if (node) pq.push(node);
    
    ListNode* dummyHead = new ListNode(0), *cur = dummyHead;
    
    while (!pq.empty()) {
        ListNode* tmp = pq.top(); pq.pop();
        cur->next = tmp; cur = cur->next;
        if (tmp->next) pq.push(tmp->next);
    }

    return dummyHead->next;
}
  • 时间复杂度：O(N log K)
  • 适用于：K 远小于 N

📌 归并 vs. 优先队列

方法时间复杂度空间复杂度适用场景
递归归并（分治法）O(N log K)O(log K)适合 K 大，N 小
优先队列（堆排序）O(N log K)O(K)适合 K 小，N 大

总结

  • 递归归并：
    ✅ 适用于 K 大、N 小的情况（如 K > 10⁵）
    ✅ 递归深度 O(log K)，空间占用少
    ✅ 时间复杂度 O(N log K)，比顺序合并快

  • 优先队列（堆）：
    ✅ 适用于 K 小、N 大的情况（如 K < 10⁴）
    ✅ 适合数据流场景，插入新链表时更快
    ❌ priority_queue 需要 O(K) 额外空间

🚀 一般情况推荐 优先队列方法，但如果 K 很大，递归归并更优！

C++ vector<int> 归并排序（Merge Sort）

归并排序是一种 分治算法（Divide and Conquer），主要步骤如下：

  1. 分解（Divide）：
    • 将 vector<int> 拆分成 左右两个子数组，直到每个子数组长度为 1。
  2. 合并（Merge）：
    • 将两个已经排序的子数组 合并为一个有序数组。

1. 递归实现 vector<int> 归并排序

#include <iostream>
#include <vector>
using namespace std;

// 合并两个有序子数组
void merge(vector<int>& arr, int left, int mid, int right) {
    vector<int> leftArr(arr.begin() + left, arr.begin() + mid + 1);
    vector<int> rightArr(arr.begin() + mid + 1, arr.begin() + right + 1);

    int i = 0, j = 0, k = left;
    while (i < leftArr.size() && j < rightArr.size()) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k++] = leftArr[i++];
        } else {
            arr[k++] = rightArr[j++];
        }
    }

    // 复制剩余元素
    while (i < leftArr.size()) arr[k++] = leftArr[i++];
    while (j < rightArr.size()) arr[k++] = rightArr[j++];
}

// 递归归并排序
void mergeSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);       // 排序左半部分
        mergeSort(arr, mid + 1, right);  // 排序右半部分
        merge(arr, left, mid, right);    // 合并两个有序子数组
    }
}

// 测试代码
int main() {
    vector<int> arr = {10, 7, 8, 9, 1, 5};

    mergeSort(arr, 0, arr.size() - 1);

    cout << "排序后数组: ";
    for (int num : arr) cout << num << " ";
    cout << endl;

    return 0;
}

2. 代码解析

（1）合并函数 merge()
  • leftArr 和 rightArr 存储 arr[left] ~ arr[mid] 和 arr[mid+1] ~ arr[right]。
  • 双指针法 依次取较小的元素，插入 arr[]。
  • 复制剩余元素（如果 leftArr 或 rightArr 还有未合并的部分）。
（2）递归排序 mergeSort()
  • 递归地将数组拆分 直到只有一个元素（left == right）。
  • 然后合并 这些小数组，最终形成完整排序数组。

3. 时间 & 空间复杂度

情况时间复杂度空间复杂度
最优情况（Best Case）O(n log n)O(n)
最坏情况（Worst Case）O(n log n)O(n)
平均情况（Average Case）O(n log n)O(n)

  • 时间复杂度 O(n log n)：

    • 归并排序将数组不断二分，每次分割 O(log n)。
    • 合并两个子数组 需要 O(n)。
    • 总体复杂度是 O(n log n)。

  • 空间复杂度 O(n)：

    • 临时数组存储左、右子数组，每轮合并占用 O(n) 额外空间。

4. 迭代实现（非递归）

如果想要 避免递归调用栈的额外空间开销，可以使用 迭代方式（非递归）：

void mergeSortIterative(vector<int>& arr) {
    int n = arr.size();
    vector<int> temp(n);

    for (int size = 1; size < n; size *= 2) { // 控制子数组大小
        for (int left = 0; left < n - size; left += 2 * size) {
            int mid = left + size - 1;
            int right = min(left + 2 * size - 1, n - 1);

            // 合并
            int i = left, j = mid + 1, k = left;
            while (i <= mid && j <= right) {
                temp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
            }
            while (i <= mid) temp[k++] = arr[i++];
            while (j <= right) temp[k++] = arr[j++];

            for (int x = left; x <= right; x++) arr[x] = temp[x];  // 复制回原数组
        }
    }
}
迭代思路
  • 第一轮：合并 大小为 1 的子数组。
  • 第二轮：合并 大小为 2 的子数组。
  • 依次倍增，直到 整个数组排序完成。
复杂度
  • 时间复杂度 O(n log n)。
  • 空间复杂度 O(n)（需要额外 temp[]）。

5. 适用场景

适用情况不适用情况
数据量大，要求稳定排序数据量小，快排更快
适用于链表排序（O(1) 额外空间）不适用于内存受限的场景（占用 O(n) 额外空间）
适用于外部排序（磁盘存储数据排序）在数组排序时，快排通常更快

6. 归并排序 vs 快速排序

排序算法时间复杂度空间复杂度是否稳定排序适用场景
归并排序O(n log n)O(n)✅ 稳定适合链表、大数据排序
快速排序O(n log n)（最坏 O(n²)）O(1)❌ 不稳定适合一般数据排序，平均比归并快

7. 总结

  • 归并排序特点

    • 稳定排序：不会改变相同元素的相对顺序。
    • 时间复杂度 O(n log n)，优于 O(n²) 的排序算法（如冒泡、选择）。
    • 空间复杂度 O(n)，比快排 O(1) 更高。

  • 何时使用归并排序？

    • 链表排序（链表归并排序可以优化到 O(1) 额外空间）。
    • 需要稳定排序（如数据库排序）。
    • 大规模数据排序（外部排序）。

对于大多数数组排序任务，快速排序 通常更快且空间占用更少，但 归并排序在链表或外部排序中表现更优。

🚀 如果数据大且要求稳定排序，推荐归并排序；如果追求更快的排序速度，使用快速排序！


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

相关文章

Megatron-LM：使用模型并行训练数十亿参数的语言模型

Megatron-LM：使用模型并行训练数十亿参数的语言模型

摘要 最近在语言建模方面的工作表明&#xff0c;训练大型Transformer模型能够推动自然语言处理应用的技术前沿。然而&#xff0c;由于内存限制&#xff0c;训练非常大的模型可能相当困难。在这项工作中&#xff0c;我们展示了训练极大Transformer模型的技术&#xff0c;并实现…
阅读更多...
GoFly框架中集成Bolt 和badfer两个Go语言嵌入式键值数据库

GoFly框架中集成Bolt 和badfer两个Go语言嵌入式键值数据库

本插件集成了Bolt 和badfer两个纯Go实现的快速的嵌入式K/V数据库&#xff0c;方便开发时本地存储使用。插件集成Bolt 和badfer两个&#xff0c;如果确定使用其中一个&#xff0c;也可以把其中不用的一个删除&#xff0c;不删除也不会有任何影响。 插件使用说明 1.安装插件 到…
阅读更多...
GitHub免密操作与跨服务器通行：SSH密钥一站式配置指南

GitHub免密操作与跨服务器通行：SSH密钥一站式配置指南

作为开发者，与GitHub的安全交互和远程服务器的高效管理是日常工作的核心技能。本文将从零开始，教你如何配置GitHub的SSH密钥认证，并实现免密码远程登录Linux服务器。 一、为什么需要SSH密钥？ 更安全的认证方式：相比传统密码，密钥认证几乎无法被暴力破解操作便捷性：免去每…
阅读更多...
设计模式教程：策略模式（Strategy Pattern）

设计模式教程：策略模式（Strategy Pattern）

一、概述 策略模式&#xff08;Strategy Pattern&#xff09; 是一种行为型设计模式&#xff0c;旨在定义一系列算法&#xff08;或行为&#xff09;&#xff0c;并将它们封装到独立的类中&#xff0c;使得它们可以互相替换。策略模式让算法的变化独立于使用算法的客户端&…
阅读更多...
一天记20个忘10个之4：man

一天记20个忘10个之4：man

据说&#xff0c;给你一个支点&#xff0c;你就能撬起地球。 那好&#xff0c;今天&#xff0c;我给你一个 man&#xff0c;如果你能完成记20个忘10个的任务&#xff0c;你就真的很 man 了。 零、热身 young manold manmedical man 一、man之复合词 1.1 man复合词 chairm…
阅读更多...
Pytorch实现论文：基于多尺度融合生成对抗网络的水下图像增强

Pytorch实现论文：基于多尺度融合生成对抗网络的水下图像增强

简介 简介：提出了一种新型的水下图像增强算法，基于多尺度融合生成对抗网络，名为UMSGAN，以解决低对比度和颜色失真的问题。首先经过亮度的处理，将处理后的图像输入设计的MFFEM模块和RM模块生成图像。该算法旨在适应各种水下场景，提供颜色校正和细节增强。 论文题目：Und…
阅读更多...
【Java毕业设计】商城购物系统（附源码+数据库脚本）

【Java毕业设计】商城购物系统（附源码+数据库脚本）

本系统是基于JavaEEServletJSPMysql实现的商城购物系统。包括用户登录、用户注册、商品分类、添加购物车、订单支付等基本功能&#xff0c;具体页面及功能如下&#xff1a; 感谢阅读&#xff01; 如需获取完整项目源码及更多项目信息&#xff0c;可添加V&#xff1a;
阅读更多...
Day 49 卡玛笔记

Day 49 卡玛笔记

这是基于代码随想录的每日打卡 1143. 最长公共子序列 给定两个字符串 text1 和 text2&#xff0c;返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 &#xff0c;返回 0 。 一个字符串的 子序列 是指这样一个新的字符串&#xff1a;它是由原字符串在不改变…
阅读更多...
最新文章

Copyright @ 2022~2023