链表排序算法c语言(链表排序算法c语言思想)

简介

链表是一种常见的数据结构，它由节点组成，每个节点包含数据和指向下一个节点的指针。链表排序算法可以根据数据的大小重新排列链表中的节点，以实现升序或降序的排序。本文将介绍三种常见的链表排序算法，包括冒泡排序、归并排序和插入排序。

冒泡排序

冒泡排序是一种简单但不高效的排序算法。它重复地遍历链表，并比较相邻节点的值，如果顺序不对则交换它们。通过多次遍历和比较，最大（或最小）的元素会逐渐"冒泡"到链表的末尾。

下面是冒泡排序的C语言实现：

void bubbleSort(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return;
    }
    struct ListNode* p, * q;
    int swapped;
    do {
        swapped = 0;
        p = head;
        while (p->next != NULL) {
            q = p->next;
            if (p->val > q->val) {
                int temp = p->val;
                p->val = q->val;
                q->val = temp;
                swapped = 1;
            }
            p = p->next;
        }
    } while (swapped);
}

冒泡排序的时间复杂度为O(n^2)，其中n是链表中节点的数量。

归并排序

归并排序是一种高效的排序算法，它将链表分成两个部分，分别对这两部分进行排序，然后再合并这两部分以得到最终的排序结果。

下面是归并排序的C语言实现：

struct ListNode* merge(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode head, * tail = &head;
    while (l1 && l2) {
        if (l1->val < l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    tail->next = l1 ? l1 : l2;
    return head.next;
}

struct ListNode* mergeSort(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    struct ListNode* mid = findMiddle(head);
    struct ListNode* l1 = head;
    struct ListNode* l2 = mid->next;
    mid->next = NULL;
    return merge(mergeSort(l1), mergeSort(l2));
}

归并排序的时间复杂度为O(nlogn)，其中n是链表中节点的数量。

插入排序

插入排序是一种简单且高效的排序算法，它逐个遍历链表中的元素，并将每个元素插入到已排序的部分中的正确位置。

下面是插入排序的C语言实现：

struct ListNode* insertionSort(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    struct ListNode dummy;
    dummy.next = head;
    struct ListNode* tail = head;
    struct ListNode* p = head->next;
    while (p != NULL) {
        if (p->val < tail->val) {
            struct ListNode* q = &dummy;
            while (q->next->val < p->val) {
                q = q->next;
            }
            tail->next = p->next;
            p->next = q->next;
            q->next = p;
            p = tail->next;
        } else {
            tail = p;
            p = p->next;
        }
    }
    return dummy.next;
}

插入排序的时间复杂度为O(n^2)，其中n是链表中节点的数量。