链表 quicksort

快速排序（Quicksort）是一种高效的排序算法，其基本思想是分而治之，通过一趟排序将待排记录分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后分别对这两部分再进行排序，整个排序过程递归进行，直到所有元素有序。

在链表上实现快速排序的主要挑战在于，链表不像数组那样可以直接访问任意位置的元素，所以我们不能像处理数组那样通过索引直接交换元素。但我们可以采用类似的方法：

1. **选择基准**：在链表中随机选择一个节点作为基准值pivot。

2. **分区操作**：遍历链表，找到小于基准的节点和大于基准的节点，分别放在两个新的链表中。这个过程可能需要创建新的链接节点，因为原链表不可修改。

3. **递归**：对小于基准的子链表和大于基准的子链表再次执行快速排序。

4. **合并**：最后，把排序后的两个子链表连接起来，并返回新形成的链表头节点。

由于链表操作涉及到节点移动而非简单的元素交换，所以快速排序的实现相比数组会稍微复杂一些，但它的时间复杂度依然保持在平均情况下为O(n log n)。

相关问题

c语言链表排序

链表排序一般采用归并排序或快速排序。

1. 归并排序

归并排序的基本思路是分治法，将链表分成若干个子链表，对每个子链表进行排序，然后合并子链表，直到最后只剩下一个有序链表。具体实现如下：

// 定义链表结构体
typedef struct ListNode {
    int val;
    struct ListNode *next;
}ListNode;

// 合并两个有序链表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (l1 == NULL) return l2;
    if (l2 == NULL) return l1;

    ListNode *head = NULL;
    ListNode *tail = NULL;

    // 将较小的结点作为头结点
    if (l1->val < l2->val) {
        head = l1;
        l1 = l1->next;
    }
    else {
        head = l2;
        l2 = l2->next;
    }

    // 遍历两个链表，依次取出较小的结点
    tail = head;
    while (l1 != NULL && l2 != NULL) {
        if (l1->val < l2->val) {
            tail->next = l1;
            l1 = l1->next;
        }
        else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }

    // 将剩余结点接到尾部
    if (l1 != NULL) {
        tail->next = l1;
    }
    else if (l2 != NULL) {
        tail->next = l2;
    }

    return head;
}

// 归并排序
ListNode* sortList(ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }

    // 快慢指针找到链表中点
    ListNode *fast = head;
    ListNode *slow = head;
    while (fast->next != NULL && fast->next->next != NULL) {
        fast = fast->next->next;
        slow = slow->next;
    }

    // 将链表分成两个子链表
    ListNode *head1 = head;
    ListNode *head2 = slow->next;
    slow->next = NULL;

    // 递归排序两个子链表
    head1 = sortList(head1);
    head2 = sortList(head2);

    // 合并两个子链表，返回头结点
    return mergeTwoLists(head1, head2);
}

2. 快速排序

快速排序的基本思路是选取一个元素作为基准值，将链表分成小于基准值和大于等于基准值的两部分，然后递归地对两部分进行快速排序。具体实现如下：

// 获取链表结点数量
int getListLength(ListNode *head) {
    int count = 0;
    while (head != NULL) {
        count++;
        head = head->next;
    }
    return count;
}

// 快速排序
ListNode* quickSort(ListNode *head, ListNode *tail) {
    if (head == NULL || head == tail) {
        return head;
    }

    // 将链表分成小于基准值和大于等于基准值的两部分
    ListNode *pivot = head;
    ListNode *p = head;
    ListNode *q = head->next;
    while (q != tail) {
        if (q->val < pivot->val) {
            p = p->next;
            int tmp = p->val;
            p->val = q->val;
            q->val = tmp;
        }
        q = q->next;
    }
    int tmp = p->val;
    p->val = pivot->val;
    pivot->val = tmp;

    // 递归地对两部分进行快速排序
    quickSort(head, p);
    quickSort(p->next, tail);

    return head;
}

// 快速排序入口函数
ListNode* sortList(ListNode* head) {
    int len = getListLength(head);
    return quickSort(head, NULL);
}

链表快速排序的递归算法

链表快速排序的递归算法可以通过以下步骤实现：

1. 选择链表中的一个元素作为基准值（pivot）。
2. 将链表分成两个部分，一个部分包含所有小于等于基准值的元素，另一个部分包含所有大于基准值的元素。
3. 对两个部分分别进行递归排序。
4. 将排序后的两个部分连接起来，得到最终排序后的链表。

下面是一个示例代码：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def partition(head, end):
    pivot = head.val
    slow = head
    fast = head.next

    while fast != end:
        if fast.val < pivot:
            slow = slow.next
            slow.val, fast.val = fast.val, slow.val
        fast = fast.next

    slow.val, head.val = head.val, slow.val
    return slow

def quickSort(head, end):
    if head != end:
        pivot = partition(head, end)
        quickSort(head, pivot)
        quickSort(pivot.next, end)

def sortList(head):
    quickSort(head, None)
    return head

这段代码中，`ListNode` 是链表节点的定义，`partition` 函数用于将链表分成两个部分，`quickSort` 函数用于递归排序，`sortList` 函数是入口函数，用于调用快速排序算法。