排序算法详解：归并排序及其在链表排序中的应用

排序算法详解：归并排序及其在链表排序中的应用

归并排序是一种高效的排序算法，它采用分治策略将数组分解成更小的子数组，然后将这些子数组合并成一个有序数组。本文将详细介绍归并排序的基本思想、步骤、代码实现、时间复杂度和空间复杂度分析，以及如何使用归并排序对链表进行排序。

思想：

归并排序的基本思想是将两个或多个有序的数组合并成一个有序数组。单个元素可以看作是一个有序数组。

步骤：

1. 将数组分解，直到每个子数组只包含一个元素（因为单个元素的数组默认是有序的）。
2. 将两两有序的子数组进行合并，重复此步骤，直到整个数组排序完成。

实现代码

#include <iostream> // 包含输入输出流头文件
#include <vector> // 包含vector头文件
using namespace std; // 使用标准命名空间

// 定义Merge函数，用于将两个有序部分合并
void Merge(vector<int>& vec, int l, int mid, int r) {
    vector<int> temp; // 创建临时向量用于存储合并后的结果
    int i = l; // 初始化左边部分的起始索引
    int j = mid + 1; // 初始化右边部分的起始索引
    // 将左右两部分按照大小顺序合并到temp中
    while (i <= mid && j <= r) {
        if (vec[i] <= vec[j]) {
            temp.push_back(vec[i]);
            i++;
        } else {
            temp.push_back(vec[j]);
            j++;
        }
    }
    // 将左边剩余的元素拷贝到temp中
    while (i <= mid) {
        temp.push_back(vec[i]);
        i++;
    }
    // 将右边剩余的元素拷贝到temp中
    while (j <= r) {
        temp.push_back(vec[j]);
        j++;
    }
    // 将合并后的结果拷贝回原始数组vec中的[l, r]区间
    i = l;
    for (auto x : temp) {
        vec[i++] = x;
    }
}

// 定义Mergesort函数，用于归并排序
void Mergesort(vector<int>& vec, int l, int r) {
    // 若当前区间只有一个元素，则返回
    if (l >= r) return;
    // 计算中间位置
    int mid = (l + r) / 2;
    // 分别对左右两部分进行归并排序
    Mergesort(vec, l, mid);
    Mergesort(vec, mid + 1, r);
    // 合并左右两部分
    Merge(vec, l, mid, r);
}

int main() {
    // 初始化待排序数组
    vector<int> vec{ 5,7,3,9,4,8,2,9,1 };
    int n = vec.size(); // 获取数组大小
    // 对数组进行归并排序
    Mergesort(vec, 0, n - 1);
    // 输出排序后的结果
    for (auto x : vec) {
        cout << x << " ";
    }
    return 0;
}

时间复杂度分析：

归并排序的效率是比较高的，设数列长为N，将数列分开成小数列一共要logN步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N)，故一共为O(N*logN)。

空间复杂度：

O(N)，归并排序需要一个与原数组相同长度的数组做辅助来排序。

扩展：（使用归并排序的思想进行链表排序）

首先将待排序的数组转换为单链表，然后使用归并排序对链表进行排序，最后输出排序后的结果。

代码实现：

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

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

// 将链表切割成前i个节点和后面的部分，并返回后面部分的头指针
ListNode* cut(ListNode* node, int i) {
    ListNode* p = node;
    // 找到第i个节点
    while (--i && p) {
        p = p->next;
    }
    // 若未找到或p为空，返回nullptr
    if (p == nullptr) return nullptr;
    ListNode* nxt = p->next;
    // 切断前i个节点和后面的部分
    p->next = nullptr;
    return nxt;
}

// 合并两个有序链表，并返回合并后的链表头指针
ListNode* merge(ListNode* l, ListNode* r) {
    ListNode* dummyhead = new ListNode; // 创建虚拟头节点
    ListNode* p = dummyhead; // 指针p指向虚拟头节点
    // 遍历两个链表，按照升序依次将节点连接到p的后面
    while (l && r) {
        if (l->val <= r->val) {
            p->next = l;
            l = l->next;
            p = p->next;
        } else {
            p->next = r;
            r = r->next;
            p = p->next;
        }
    }
    // 将剩余的节点连接到p的后面
    if (l) {
        p->next = l;
    }
    if (r) {
        p->next = r;
    }
    return dummyhead->next; // 返回合并后的链表头指针
}

// 对链表进行归并排序
ListNode* ListMergeSort(ListNode* head) {
    int length = 0; // 记录链表长度
    ListNode* p = head; // 指针p指向链表头节点
    // 计算链表长度
    while (p) {
        p = p->next;
        length++;
    }
    // 创建虚拟头节点，并指向原始链表头节点
    ListNode* dummyhead = new ListNode;
    dummyhead->next = head;
    // 外层循环，每次将链表分成长度为i的段，i从1开始，每次翻倍，直到超过链表长度
    for (int i = 1; i < length; i *= 2) {
        ListNode* cur = dummyhead->next; // 指针cur指向当前待合并的段的头节点
        ListNode* tail = dummyhead; // 指针tail指向合并后的段的尾节点
        while (cur) {
            ListNode* left = cur; // 左半部分的头节点
            ListNode* right = cut(left, i); // 右半部分的头节点
            cur = cut(right, i); // 更新cur指向下一个待合并的段的头节点
            tail->next = merge(left, right); // 将左右两部分合并后连接到已排序部分的尾部
            while (tail->next) {
                tail = tail->next; // 移动tail到已排序部分的尾部
            }
        }
    }
    return dummyhead->next; // 返回排序后的链表头指针
}

int main() {
    // 初始化待排序数组
    vector<int> vec{ 5,7,3,9,4,8,2,9,1 };
    // 创建虚拟头节点
    ListNode* dummyhead = new ListNode;
    ListNode* cur = dummyhead;
    // 将待排序数组转换为链表
    for (auto x : vec) {
        ListNode* newnode = new ListNode;
        newnode->val = x;
        cur->next = newnode;
        cur = cur->next;
    }
    // 对链表进行归并排序
    cur = ListMergeSort(dummyhead->next);
    // 输出排序后的结果
    while (cur) {
        cout << cur->val << " ";
        cur = cur->next;
    }
    return 0;
}