如何使用C语言实现链式表排序

在C语言中，链表排序通常可以使用插入排序、冒泡排序、选择排序或归并排序等算法实现。这里以插入排序为例，因为它的思想简单直观，适合对小规模数据或部分有序的数据进行操作。

**插入排序链表算法步骤：**
1. 定义一个结构体表示链表节点，包含数据域和指向下一个节点的指针。
2. 定义两个指针，`current` 和 `prev` 分别初始化为链表头和空指针。
3. 创建一个临时变量 `temp`，用于存储当前节点的数据。
4. 遍历链表，从第二个节点开始（第一个已视为有序）：
- 将 `current` 指向的节点的数据与前一个节点进行比较。
- 如果 `current->data` 小于 `prev->data` 或者 `prev` 为空，则无需移动，继续遍历下一个节点。
- 否则，将 `prev->next` 设置为 `current`，然后依次将 `prev` 和 `current` 移动到它们应该的位置，直到找到合适的位置或到达链表末尾。
5. 当遍历完整个链表后，链表即按照升序排列。

下面是简化版的C代码示例：

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

void insertionSortList(Node** head) {
    if (*head == NULL || (*head)->next == NULL) return; // 如果链表为空或只有一个元素，直接返回

    Node* current = *head->next;
    Node* prev = *head;

    while (current != NULL) {
        Node* temp = current;
        if (temp->data < prev->data) {
            current = current->next;
            continue;
        }
        
        // 插入操作
        prev->next = temp->next;
        while (prev->next != NULL && prev->next->data < temp->data) {
            prev = prev->next;
        }
        temp->next = prev->next;
        prev->next = temp;
        
        current = temp->next;
    }
}

// 使用示例
Node* head = createLinkedList(); // 初始化链表
insertionSortList(&head); // 排序