写一个C语言的链表排序

可以使用快速排序算法来对C语言中的链表进行排序，其基本思想是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

相关问题

能一个C语言链表排序的demo吗

可以，以下是一个简单的链表排序的示例代码：

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

void insert(Node** head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;

    if (*head == NULL) {
        *head = newNode;
    } else {
        Node* current = *head;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = newNode;
    }
}

void printList(Node* head) {
    Node* current = head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

void swap(Node* a, Node* b) {
    int temp = a->data;
    a->data = b->data;
    b->data = temp;
}

void bubbleSort(Node* head) {
    int swapped;
    Node* ptr1;
    Node* lptr = NULL;

    if (head == NULL) {
        return;
    }

    do {
        swapped = ;
        ptr1 = head;

        while (ptr1->next != lptr) {
            if (ptr1->data > ptr1->next->data) {
                swap(ptr1, ptr1->next);
                swapped = 1;
            }
            ptr1 = ptr1->next;
        }
        lptr = ptr1;
    } while (swapped);
}

int main() {
    Node* head = NULL;

    insert(&head, 5);
    insert(&head, 3);
    insert(&head, 8);
    insert(&head, 1);
    insert(&head, 6);

    printf("Before sorting: ");
    printList(head);

    bubbleSort(head);

    printf("After sorting: ");
    printList(head);

    return ;
}

这个示例代码演示了如何使用冒泡排序算法对链表进行排序。

c语言链表排序

链表排序一般采用归并排序或快速排序。

1. 归并排序

归并排序的基本思路是分治法，将链表分成若干个子链表，对每个子链表进行排序，然后合并子链表，直到最后只剩下一个有序链表。具体实现如下：

// 定义链表结构体
typedef struct ListNode {
    int val;
    struct ListNode *next;
}ListNode;

// 合并两个有序链表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (l1 == NULL) return l2;
    if (l2 == NULL) return l1;

    ListNode *head = NULL;
    ListNode *tail = NULL;

    // 将较小的结点作为头结点
    if (l1->val < l2->val) {
        head = l1;
        l1 = l1->next;
    }
    else {
        head = l2;
        l2 = l2->next;
    }

    // 遍历两个链表，依次取出较小的结点
    tail = head;
    while (l1 != NULL && l2 != NULL) {
        if (l1->val < l2->val) {
            tail->next = l1;
            l1 = l1->next;
        }
        else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }

    // 将剩余结点接到尾部
    if (l1 != NULL) {
        tail->next = l1;
    }
    else if (l2 != NULL) {
        tail->next = l2;
    }

    return head;
}

// 归并排序
ListNode* sortList(ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }

    // 快慢指针找到链表中点
    ListNode *fast = head;
    ListNode *slow = head;
    while (fast->next != NULL && fast->next->next != NULL) {
        fast = fast->next->next;
        slow = slow->next;
    }

    // 将链表分成两个子链表
    ListNode *head1 = head;
    ListNode *head2 = slow->next;
    slow->next = NULL;

    // 递归排序两个子链表
    head1 = sortList(head1);
    head2 = sortList(head2);

    // 合并两个子链表，返回头结点
    return mergeTwoLists(head1, head2);
}

2. 快速排序

快速排序的基本思路是选取一个元素作为基准值，将链表分成小于基准值和大于等于基准值的两部分，然后递归地对两部分进行快速排序。具体实现如下：

// 获取链表结点数量
int getListLength(ListNode *head) {
    int count = 0;
    while (head != NULL) {
        count++;
        head = head->next;
    }
    return count;
}

// 快速排序
ListNode* quickSort(ListNode *head, ListNode *tail) {
    if (head == NULL || head == tail) {
        return head;
    }

    // 将链表分成小于基准值和大于等于基准值的两部分
    ListNode *pivot = head;
    ListNode *p = head;
    ListNode *q = head->next;
    while (q != tail) {
        if (q->val < pivot->val) {
            p = p->next;
            int tmp = p->val;
            p->val = q->val;
            q->val = tmp;
        }
        q = q->next;
    }
    int tmp = p->val;
    p->val = pivot->val;
    pivot->val = tmp;

    // 递归地对两部分进行快速排序
    quickSort(head, p);
    quickSort(p->next, tail);

    return head;
}

// 快速排序入口函数
ListNode* sortList(ListNode* head) {
    int len = getListLength(head);
    return quickSort(head, NULL);
}