双向链表的快速排序函数

 链表的节点作为快速排序的元素，通过节点的指针进行操作，而不是通过数组索引 

public void quickSort(int[] arr, int left, int right){
        if(left < right){
            int pos = partition(arr, left, right);
            quickSort(arr, left, pos - 1);
            quickSort(arr, pos + 1, right);
        }
    }
public int partition(int[] arr, int left, int right){
        int base = arr[left];
        while(left < right){
            while(left < right && arr[right] >= base){
                right--;
            }
            arr[left] = arr[right];
            while(left < right && arr[left] <= base){
                left++;
            }
            arr[right] = arr[left];       
        }
        arr[left] = base;
        return left;
    }
}

思路

1. 选基准：选择链表的最后一个节点作为基准值。
2. 初始化指针：low 指向链表的第一个节点，high 指向链表的最后一个节点。
3. 划分：(遍历链表，将小于基准值的节点移动到基准值左侧，将大于基准值的节点移动到基准值右侧)
   • 指针 i j遍历链表，i 从 low 的前节点开始，j 从 low 开始。
   • 如果 j 指向的节点数据小于基准值，则 i 向后移一位，并交换 i 和 j 指向节点数据。
   • 移动 j，直到 j 和 high 相邻。
   • 交换 i 的下一个节点和 high 的数据。
4. 递归排序：(对基准值左侧和右侧的子链表分别进行快速排序)
   • 对 low 到 i 的前一个节点进行快速排序。
   • 对 i 的下一个节点到 high 进行快速排序。

代码

// 节点结构体
typedef struct DoublyLinkedListNode {
    int data;
    struct DoublyLinkedListNode *prev;
    struct DoublyLinkedListNode *next;
} DoublyLinkedListNode;

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

// 尾插
void appendNode(DoublyLinkedListNode** head, int data) {
    DoublyLinkedListNode* newNode = createNode(data);
    if (*head == NULL) {// 如果链表为空
        *head = newNode; // 新节点成为头节点
        return;
    }
    DoublyLinkedListNode* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->prev = temp;
}

// 交换节点的数据
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 获取链表最后节点
DoublyLinkedListNode* getLastNode(DoublyLinkedListNode* head) {
    while (head && head->next) {
        head = head->next;
    }
    return head;
}

// 快速排序的划分函数
DoublyLinkedListNode* partition(DoublyLinkedListNode* low, DoublyLinkedListNode* high) {
    int base = high->data;
    DoublyLinkedListNode* i = low->prev;

    for (DoublyLinkedListNode* j = low; j != high; j = j->next) {
        if (j->data <=base) {// 如果当前节点数据小于等于基准值
            i = (i == NULL) ? low : i->next;
            swap(&(i->data), &(j->data));
        }
    }
    i = (i == NULL) ? low : i->next;
    swap(&(i->data), &(high->data));
    return i;//划分后的基准位置
}

// 快速排序函数
void quickSort(DoublyLinkedListNode* low, DoublyLinkedListNode* high) {
    if (high != NULL && low != high && low != high->next) { //至少有两个节点
        DoublyLinkedListNode* p = partition(low, high); // 划分链表
        quickSort(low, p->prev);// 递归排序左子链表
        quickSort(p->next, high);
    }
}

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

int main() {
    DoublyLinkedListNode* head = NULL;// 初始化链表头指针
    appendNode(&head, 4);
    appendNode(&head, 2);
    appendNode(&head, 5);
    appendNode(&head, 3);
    appendNode(&head, 1);

    printf("排序前: ");
    printList(head);

    quickSort(head, getLastNode(head));

    printf("排序后: ");
    printList(head);

    return 0;
}

运行结果