c语言双向链表快速排序

以下是 C 语言双向链表的快速排序实现：

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

typedef struct node {
    int val;
    struct node *prev;
    struct node *next;
} Node;

Node *partition(Node *head, Node *tail) {
    int pivot = tail->val;
    Node *i = head->prev;
    for (Node *j = head; j != tail; j = j->next) {
        if (j->val <= pivot) {
            i = (i == NULL) ? head : i->next;
            int tmp = i->val;
            i->val = j->val;
            j->val = tmp;
        }
    }
    i = (i == NULL) ? head : i->next;
    int tmp = i->val;
    i->val = tail->val;
    tail->val = tmp;
    return i;
}

void quick_sort(Node *head, Node *tail) {
    if (tail != NULL && head != tail && head != tail->next) {
        Node *p = partition(head, tail);
        quick_sort(head, p->prev);
        quick_sort(p->next, tail);
    }
}

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

int main() {
    Node *head = (Node *)malloc(sizeof(Node));
    head->val = 5;
    head->prev = NULL;
    head->next = (Node *)malloc(sizeof(Node));
    head->next->val = 2;
    head->next->prev = head;
    head->next->next = (Node *)malloc(sizeof(Node));
    head->next->next->val = 8;
    head->next->next->prev = head->next;
    head->next->next->next = (Node *)malloc(sizeof(Node));
    head->next->next->next->val = 3;
    head->next->next->next->prev = head->next->next;
    head->next->next->next->next = NULL;

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

    quick_sort(head, head->next->next->next);

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

    return 0;
}

解释：

- `partition` 函数实现了快速排序的分区操作，其输入参数为链表头和尾节点，返回值为分区点；
- `quick_sort` 函数实现了快速排序的递归操作；
- `print_list` 函数用于打印链表；
- 在 `main` 函数中初始化了一个双向链表，并对其进行排序。

注意：

- 在 `partition` 函数中，我们选择尾节点作为基准点（pivot），这是快速排序的常规选择；
- 在 `partition` 函数中，我们使用了一种经典的双指针算法，分别指向小于等于基准点和大于基准点的元素；
- 在 `partition` 函数中，我们使用了链表节点值的交换，而不是节点指针的交换，因为我们需要维护链表节点的 prev 和 next 指针；
- 在 `quick_sort` 函数中，我们需要判断链表头和尾是否相等，以及链表头是否为尾的下一个节点，这是递归终止条件；
- 在 `main` 函数中，我们需要手动创建链表并初始化，这是为了方便演示。在实际应用中，链表可能是从其他函数或模块中传入的，或者是动态创建的。