详解C++实现链表的排序算法

算法介绍

链表是一种常见的数据结构，在实际使用中常常需要对链表进行排序。本文将介绍在C++中实现链表排序的几种算法，包括插入排序，归并排序和快速排序。

插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法。具体实现过程如下：

1. 遍历链表，取下一个节点作为插入节点。
2. 如果当前节点不小于插入节点，则将插入节点插入到当前节点之前。
3. 如果已经到达链表尾部，则将插入节点插入到链表尾部。

该算法的时间复杂度为O(n^2)，其中被比较的元素的数量为n(n-1)/2。算法的空间复杂度为O(1)。

归并排序

归并排序（Merge Sort）是一种分治算法，其具体实现过程如下：

1. 递归划分链表，直到链表只剩下一个节点。
2. 将两个已排序的链表合并成一个链表。

该算法的时间复杂度为O(nlogn)，空间复杂度为O(n)。

快速排序

快速排序（Quick Sort）是一种基于比较的排序算法，其具体实现过程如下：

1. 选择枢纽，将链表中所有元素分为两部分，一部分小于等于枢纽，另一部分大于枢纽。
2. 递归排序两个子序列。

该算法的时间复杂度最好为O(nlogn)，最坏为O(n^2)，平均为O(nlogn)。空间复杂度为O(logn)。

代码示例

以下是三种排序算法的C++代码示例：

插入排序

void insertionSort(ListNode* head) {
    if (!head || !head->next) {
        return;
    }
    ListNode* p = head->next, *q, *r;
    head->next = nullptr;
    while (p) {
        q = p->next;
        r = head;
        while (r->next && r->next->val < p->val) {
            r = r->next;
        }
        p->next = r->next;
        r->next = p;
        p = q;
    }
}

归并排序

ListNode* mergeSort(ListNode* head) {
    if (!head || !head->next) {
        return head;
    }
    ListNode* p = head, *q = head->next;
    while (q && q->next) {
        p = p->next;
        q = q->next->next;
    }
    ListNode* right = mergeSort(p->next);
    p->next = nullptr;
    ListNode* left = mergeSort(head);
    return merge(left, right);
}

ListNode* merge(ListNode* l1, ListNode* l2) {
    if (!l1) {
        return l2;
    }
    if (!l2) {
        return l1;
    }
    if (l1->val < l2->val) {
        l1->next = merge(l1->next, l2);
        return l1;
    } else {
        l2->next = merge(l1, l2->next);
        return l2;
    }
}

快速排序

ListNode* quickSort(ListNode* head) {
    if (!head || !head->next) {
        return head;
    }
    ListNode* p = head->next, *q = head;
    while (p) {
        if (p->val < head->val) {
            q = q->next;
            std::swap(q->val, p->val);
        }
        p = p->next;
    }
    std::swap(q->val, head->val);
    q->next = quickSort(q->next);
    head = quickSort(head);
    return head;
}

示例说明

假设有一个链表[5,3,7,2,9]，我们可以使用以下代码对其进行排序：

ListNode* head = new ListNode(5);
head->next = new ListNode(3);
head->next->next = new ListNode(7);
head->next->next->next = new ListNode(2);
head->next->next->next->next = new ListNode(9);
// 使用插入排序进行排序
insertionSort(head);
// 使用归并排序进行排序
head = mergeSort(head);
// 使用快速排序进行排序
head = quickSort(head);

以上示例演示了如何在C++中使用插入排序、归并排序和快速排序对链表进行排序。