C语言对单链表进行快速排序实现。
时间: 2024-02-21 09:22:01 浏览: 116
下面是使用C语言对单链表进行快速排序的实现示例:
```c
#include<stdio.h>
#include<stdlib.h>
// 定义链表节点结构
struct ListNode {
int val;
struct ListNode *next;
};
// 快速排序的辅助函数,用于交换两个链表节点的值
void swap(struct ListNode *a, struct ListNode *b) {
int temp = a->val;
a->val = b->val;
b->val = temp;
}
// 快速排序的分割函数
struct ListNode* partition(struct ListNode *start, struct ListNode *end) {
int pivot = start->val;
struct ListNode *i = start;
struct ListNode *j = start->next;
while (j != end) {
if (j->val < pivot) {
i = i->next;
swap(i, j);
}
j = j->next;
}
swap(start, i);
return i;
}
// 快速排序的递归函数
void quickSort(struct ListNode *start, struct ListNode *end) {
if (start != end && start->next != end) {
struct ListNode *pivot = partition(start, end);
quickSort(start, pivot);
quickSort(pivot->next, end);
}
}
// 对链表进行快速排序
struct ListNode* sortList(struct ListNode* head) {
quickSort(head, NULL);
return head;
}
// 创建一个新节点
struct ListNode* createNode(int val) {
struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
newNode->val = val;
newNode->next = NULL;
return newNode;
}
// 在链表末尾插入一个节点
void insertNode(struct ListNode** head, int val) {
struct ListNode* newNode = createNode(val);
if (*head == NULL) {
*head = newNode;
return;
}
struct ListNode* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
// 打印链表
void printList(struct ListNode* head) {
struct ListNode* temp = head;
while (temp != NULL) {
printf("%d ", temp->val);
temp = temp->next;
}
printf("\n");
}
int main() {
struct ListNode* head = NULL;
// 插入一些测试数据
insertNode(&head, 3);
insertNode(&head, 1);
insertNode(&head, 7);
insertNode(&head, 5);
insertNode(&head, 2);
printf("原始链表:");
printList(head);
head = sortList(head);
printf("排序后的链表:");
printList(head);
return 0;
}
```
这段代码实现了对单链表进行快速排序的功能。首先定义了链表节点的结构,然后实现了交换两个节点值的辅助函数`swap`以及快速排序的分割函数`partition`。接下来,通过递归调用`quickSort`函数实现对链表的快速排序,最后实现了创建节点、插入节点、打印链表的辅助函数。在`main`函数中,插入了一些测试数据,然后调用`sortList`函数进行排序,并打印排序后的链表。
阅读全文