C++程序单向链表快速排序

在实际编程中，快速排序（quicksort）是非常常见的排序算法，这篇文章介绍的是如何在C++中实现单向链表快速排序。

单向链表排序的步骤

单向链表快速排序的步骤如下：

找到链表的中间结点，以此作为分割点。
将链表分为两部分，一部分包括所有小于分割点的结点，另一部分包括所有大于等于分割点的结点。
对这两部分分别递归地进行快速排序。
将两个排序后的子链表合并起来。

C++程序实现

下面的C++程序演示了如何通过单向链表快速排序来对链表进行排序。

#include <iostream>
#include <cstdlib>
using namespace std;

struct Node {
    int val;
    Node *next;
    Node(int x) : val(x), next(NULL) {}
};

Node* partition(Node* head, Node* end, Node** newHead, Node** newEnd) {
    Node *pivot = end;
    Node *prev = NULL, *cur = head, *tail = pivot;

    while (cur != pivot) {
        if (cur->val < pivot->val) {
            if ((*newHead) == NULL)
                (*newHead) = cur;
            prev = cur;
            cur = cur->next;
        } else {
            if (prev)
                prev->next = cur->next;
            Node *tmp = cur->next;
            cur->next = NULL;
            tail->next = cur;
            tail = cur;
            cur = tmp;
        }
    }

    if ((*newHead) == NULL)
        (*newHead) = pivot;
    (*newEnd) = tail;

    return pivot;
}

Node* quickSortRecur(Node* head, Node* end) {
    if (!head || head == end)
        return head;

    Node *newHead = NULL, *newEnd = NULL;
    Node *pivot = partition(head, end, &newHead, &newEnd);

    if (newHead != pivot) {
        Node *tmp = newHead;
        while (tmp->next != pivot)
            tmp = tmp->next;
        tmp->next = NULL;
        newHead = quickSortRecur(newHead, tmp);
        tmp = getTail(newHead);
        tmp->next =  pivot;
    }
    pivot->next = quickSortRecur(pivot->next, newEnd);

    return newHead;
}

Node* quickSort(Node *head) {
    return quickSortRecur(head, getTail(head));
}

void printList(Node *node) {
    while (node != NULL) {
        cout << node->val << " ";
        node = node->next;
    }
    cout << endl;
}

void push(Node** head_ref, int new_data) {
    Node* new_node = new Node(new_data);
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

Node *getTail(Node *cur) {
    while (cur != NULL && cur->next != NULL)
        cur = cur->next;
    return cur;
}

int main() {
    Node *head = NULL;
    push(&head, 6);
    push(&head, 9);
    push(&head, 1);
    push(&head, 5);
    push(&head, 2);
    push(&head, 3);
    push(&head, 8);
    push(&head, 4);

    cout << "Before sorting: ";
    printList(head);
    head = quickSort(head);
    cout << "After sorting: ";
    printList(head);

    return 0;
}

在上面的程序中，quickSortRecur()是快速排序的核心方法，它调用partition()方法完成分割操作，并使用递归调用对分割后的两个子链表进行排序，最后将排序后的子链表合并起来。