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

加粗样式

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) 额外空间）。
  • 需要稳定排序（如数据库排序）。
  • 大规模数据排序（外部排序）。

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

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