使用快速排序对一个链表进行排序C语言
时间: 2024-03-04 14:24:14 浏览: 20
快速排序的思想是选取一个基准元素,将链表中小于基准元素的节点放在左边,大于等于基准元素的节点放在右边,然后对左右两个子链表递归进行快速排序。具体实现如下:
```c
#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* partition(struct ListNode* begin, struct ListNode* end) {
int pivot = begin->val;
struct ListNode *p = begin, *q = begin->next;
while (q != end) {
if (q->val < pivot) {
p = p->next;
int temp = p->val;
p->val = q->val;
q->val = temp;
}
q = q->next;
}
int temp = begin->val;
begin->val = p->val;
p->val = temp;
return p;
}
void quickSortListRecursively(struct ListNode* begin, struct ListNode* end) {
if (begin != end && begin->next != end) {
struct ListNode *mid = partition(begin, end);
quickSortListRecursively(begin, mid);
quickSortListRecursively(mid->next, end);
}
}
struct ListNode* sortList(struct ListNode* head) {
quickSortListRecursively(head, NULL);
return head;
}
int main() {
struct ListNode *head = (struct ListNode*)malloc(sizeof(struct ListNode));
head->val = 5;
head->next = (struct ListNode*)malloc(sizeof(struct ListNode));
head->next->val = 3;
head->next->next = (struct ListNode*)malloc(sizeof(struct ListNode));
head->next->next->val = 7;
head->next->next->next = (struct ListNode*)malloc(sizeof(struct ListNode));
head->next->next->next->val = 1;
head->next->next->next->next = NULL;
head = sortList(head);
while (head) {
printf("%d ", head->val);
head = head->next;
}
return 0;
}
```
这里使用了递归实现快速排序,其中 `partition` 函数用于划分链表、选取基准元素,并将小于基准元素的节点放在左边,大于等于基准元素的节点放在右边。最后 `sortList` 函数用于对整个链表进行快速排序。