c语言折半插入排序法双链表

折半插入排序是一种高效的排序算法，而双向链表则是一种支持双向遍历的数据结构。下面是使用折半插入排序法对双链表进行排序的示例代码：

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

// 定义双向链表节点
typedef struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
} Node;

// 定义双向链表
typedef struct List {
    Node* head;
    Node* tail;
} List;

// 初始化双向链表
List* initList() {
    List* list = (List*)malloc(sizeof(List));
    list->head = NULL;
    list->tail = NULL;
    return list;
}

// 创建新节点
Node* createNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

// 在链表尾部插入新节点
void insertNode(List* list, Node* node) {
    if (list->head == NULL) {
        list->head = node;
        list->tail = node;
    } else {
        node->prev = list->tail;
        list->tail->next = node;
        list->tail = node;
    }
}

// 折半插入排序
void insertionSort(List* list) {
    Node* current = list->head->next;
    while (current != NULL) {
        Node *p = list->head, *q = current->prev;
        while (p != current && p->data <= current->data) {
            p = p->next;
        }
        while (q != p) {
            q->next->data = q->data;
            q = q->prev;
        }
        p->data = current->data;
        current = current->next;
    }
}

// 打印链表
void printList(List* list) {
    Node* current = list->head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

int main() {
    List* list = initList();
    insertNode(list, createNode(5));
    insertNode(list, createNode(3));
    insertNode(list, createNode(8));
    insertNode(list, createNode(1));
    insertNode(list, createNode(2));
    printf("Original list: ");
    printList(list);
    insertionSort(list);
    printf("Sorted list: ");
    printList(list);
    return 0;
}

这段代码中，我们首先定义了一个双向链表节点 `Node` 和一个双向链表 `List`。然后，我们实现了双向链表的初始化、创建新节点、在链表尾部插入新节点、折半插入排序、打印链表等功能。在 `insertionSort` 函数中，我们使用了折半插入排序的算法对双向链表进行排序。最后，我们调用 `main` 函数来测试我们的代码。