c语言单链表排序z多种方法
时间: 2023-12-07 19:06:03 浏览: 66
以下是几种C语言单链表排序的方法:
1. 冒泡排序法:对于链表中的每个节点,比较其与后面节点的值大小,如果前面节点的值大于后面节点的值,则交换它们的值。重复以上步骤,直到链表中的所有节点都被排序。
2. 选择排序法:从链表的头节点开始,依次遍历每个节点,找到链表中最小的节点,然后将其与当前节点交换。重复以上步骤,直到链表中的所有节点都被排序。
3. 插入排序法:从链表的第二个节点开始,将这个节点与前面的节点进行比较,如果前面的节点的值大于这个节点的值,则将前面的节点后移一个位置,直到找到一个比这个节点小的节点,然后将这个节点插入到这个节点之后。重复以上步骤,直到链表中的所有节点都被排序。
注意,在使用这些排序算法时,需要考虑链表节点的指针操作,以确保节点的正确排序。同时,为了提高排序效率,可以选择合适的数据结构和算法,以及优化算法的实现。
相关问题
c语言单链表排序
以下是使用冒泡排序算法对单链表进行排序的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义单链表结构体
typedef struct node {
int data;
struct node *next;
} Node;
// 冒泡排序函数
void bubble_sort(Node *head) {
Node *p, *q, *tail = NULL;
int exchange = 1;
while (exchange && head->next != tail) {
exchange = 0;
p = head;
q = p->next;
while (q != tail) {
if (p->data > q->data) {
int tmp = p->data;
p->data = q->data;
q->data = tmp;
exchange = 1;
}
p = p->next;
q = q->next;
}
tail = p;
}
}
// 创建单链表函数
Node *create_list(int n) {
Node *head = NULL, *tail = NULL, *p;
int i, x;
for (i = 1; i <= n; i++) {
printf("请输入第%d个节点的值:", i);
scanf("%d", &x);
p = (Node *)malloc(sizeof(Node));
p->data = x;
p->next = NULL;
if (head == NULL) {
head = p;
} else {
tail->next = p;
}
tail = p;
}
return head;
}
// 输出单链表函数
void print_list(Node *head) {
Node *p = head;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
}
// 主函数
int main() {
int n;
Node *head;
printf("请输入节点个数:");
scanf("%d", &n);
head = create_list(n);
printf("排序前的单链表为:");
print_list(head);
bubble_sort(head);
printf("\n排序后的单链表为:");
print_list(head);
return 0;
}
```
其中,`bubble_sort()` 函数使用冒泡排序算法对单链表进行排序。`create_list()` 函数用于创建包含 `n` 个节点的单链表,并返回头结点指针。`print_list()` 函数用于输出单链表中的所有节点值。在 `main()` 函数中,先调用 `create_list()` 函数创建单链表,然后输出排序前的单链表,调用 `bubble_sort()` 函数进行排序,最后输出排序后的单链表。
c语言单链表快速排序
以下是使用C语言实现单链表快速排序的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义单链表结构体
typedef struct Node {
int data;
struct Node* next;
} Node;
// 创建新节点
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// 将节点插入到链表末尾
void insertNode(Node** head, int data) {
Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
} else {
Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
}
// 交换两个节点的数据
void swap(Node* a, Node* b) {
int temp = a->data;
a->data = b->data;
b->data = temp;}
// 找到链表的中间节点
Node* getMiddle(Node* head, Node* end) {
if (head == NULL) {
return head;
}
Node* slow = head;
Node* fast = head->next;
while (fast != end) {
fast = fast->next;
if (fast != end) {
slow = slow->next;
fast = fast->next;
}
}
return slow;
}
// 快速排序的递归函数
void quickSortUtil(Node* head, Node* end) {
if (head == end || head->next == end) {
return;
}
Node* pivotPrev = getMiddle(head, end);
Node* pivot = pivotPrev->next;
Node* curr = pivot->next;
Node* tail = end;
while (curr != tail) {
if (curr->data < pivot->data) {
swap(curr, head->next);
head = head->next;
} else {
curr = curr->next;
}
}
swap(pivot, head);
quickSortUtil(head, pivotPrev);
quickSortUtil(pivot->next, end);
}
// 快速排序函数
void quickSort(Node** head) {
quickSortUtil(*head, NULL);
}
// 打印链表
void printList(Node* head) {
Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
int main() {
Node* head = NULL;
insertNode(&head, 5);
insertNode(&head, 2);
insertNode(&head, 8);
insertNode(&head, 1);
insertNode(&head, 6);
printf("排序前的链表:");
printList(head);
quickSort(&head);
printf("排序后的链表:");
printList(head);
return 0;
}
```