请用c语言写两种双向链表排序算法

当涉及到双向链表的排序算法时，常见的方法有插入排序和归并排序。以下是使用C语言实现这两种算法的示例代码。

1. 插入排序（Insertion Sort）：

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

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

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

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

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

void freeList(Node* head) {
    Node* current = head;
    while (current != NULL) {
        Node* temp = current->next;
        free(current);
        current = temp;
    }
}

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);

    // 插入排序
    for (Node* i = head->next; i != NULL; i = i->next) {
        int key = i->data;
        Node* j = i->prev;
        while (j != NULL && j->data > key) {
            j->next->data = j->data;
            j = j->prev;
        }
        if (j == NULL) {
            head->data = key;
        } else {
            j->next->data = key;
        }
    }

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

    freeList(head);

    return 0;
}

2. 归并排序（Merge Sort）：

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

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

Node* merge(Node* left, Node* right) {
    Node dummy;
    Node* tail = &dummy;

    while (left != NULL && right != NULL) {
        if (left->data <= right->data) {
            tail->next = left;
            left->prev = tail;
            left = left->next;
        } else {
            tail->next = right;
            right->prev = tail;
            right = right->next;
        }
        tail = tail->next;
        tail->prev = NULL;
    }

    if (left != NULL) {
        tail->next = left;
        left->prev = tail;
    } else {
        tail->next = right;
        right->prev = tail;
    }

    return dummy.next;
}

Node* mergeSort(Node* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }

    Node* slow = head;
    Node* fast = head->next;

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }

    Node* right = slow->next;
    slow->next = NULL;

    Node* left = mergeSort(head);
    right = mergeSort(right);

    return merge(left, right);
}

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

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

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

void freeList(Node* head) {
    Node* current = head;
    while (current != NULL) {
        Node* temp = current->next;
        free(current);
        current = temp;
    }
}

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);

    // 归并排序
    head = mergeSort(head);

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

    freeList(head);

    return 0;
}

这两种算法都可以对双向链表进行排序，插入排序每次将一个元素插入到已排序的部分，而归并排序则将链表分割为较小的部分并进行合并。您可以根据需要选择适合您情况的算法。