用c语言写出带头节点的直接插入排序算法代码

在C语言中，带头节点的直接插入排序算法通常适用于链表结构。以下是插入排序的基本思路，对于每个节点，我们会遍历已排序的部分，将它插入到正确的位置：

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

// 定义单向链表节点结构体
typedef struct ListNode {
    int data;
    struct ListNode* next;
} ListNode;

// 插入节点函数
void insertNode(ListNode** head, int data) {
    // 创建新节点
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->data = data;
    newNode->next = *head;

    // 插入节点
    ListNode* current = *head;
    while (current->next != NULL && current->next->data < data) {
        current = current->next;
    }
    newNode->next = current->next;
    current->next = newNode;
}

// 示例排序函数（链表头部）
void insertionSortLinkedList(ListNode** head) {
    if (*head == NULL || (*head)->next == NULL) {
        return; // 如果链表为空或者只有一个元素，无需排序
    }

    ListNode* sortedList = *head;
    ListNode* unsortedList = sortedList->next;

    while (unsortedList != NULL) {
        insertNode(&sortedList, unsortedList->data);
        unsortedList = unsortedList->next;
    }
}

// 测试代码
int main() {
    // 初始化链表，这里仅作演示
    ListNode* head = (ListNode*)malloc(sizeof(ListNode));
    head->data = 5;
    head->next = (ListNode*)malloc(sizeof(ListNode));
    head->next->data = 2;
    head->next->next = (ListNode*)malloc(sizeof(ListNode));
    head->next->next->data = 4;
    head->next->next->next = (ListNode*)malloc(sizeof(ListNode));
    head->next->next->next->data = 1;
    head->next->next->next->next = (ListNode*)malloc(sizeof(ListNode));
    head->next->next->next->next->data = 3;

    insertionSortLinkedList(&head);
    
    ListNode* temp = head;
    printf("Sorted Linked List:\n");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");

    return 0;
}