链表排序是数据结构中一个常见且实用的操作。在C语言中,我们可以通过多种方式对链表进行排序。本文将详细介绍几种常见的链表排序算法,并提供详细的代码示例,帮助您轻松入门链表排序。
1. 链表排序概述
链表是一种非线性数据结构,由一系列节点组成,每个节点包含数据和指向下一个节点的指针。链表排序的目标是将链表中的节点按照某种顺序排列,如升序或降序。
2. 常见的链表排序算法
2.1 冒泡排序
冒泡排序是一种简单的排序算法,它重复地遍历要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。
2.1.1 冒泡排序算法步骤
- 从第一个元素开始,比较相邻的两个元素。
- 如果第一个比第二个大(升序排序),就交换它们两个。
- 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤,除了最后已经排序好的元素。
- 重复步骤1~4,直到排序完成。
2.1.2 冒泡排序代码示例
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
struct ListNode {
int val;
struct ListNode *next;
};
// 创建新节点
struct ListNode* createNode(int val) {
struct ListNode *node = (struct ListNode*)malloc(sizeof(struct ListNode));
node->val = val;
node->next = NULL;
return node;
}
// 冒泡排序
void bubbleSort(struct ListNode *head) {
if (head == NULL || head->next == NULL) {
return;
}
struct ListNode *i, *j;
int swapped;
for (i = head; i != NULL; i = i->next) {
swapped = 0;
for (j = i->next; j != NULL; j = j->next) {
if (i->val > j->val) {
// 交换节点值
int temp = i->val;
i->val = j->val;
j->val = temp;
swapped = 1;
}
}
// 如果在这一轮没有发生交换,说明链表已经排序完成
if (swapped == 0) {
break;
}
}
}
// 打印链表
void printList(struct ListNode *node) {
while (node != NULL) {
printf("%d ", node->val);
node = node->next;
}
printf("\n");
}
// 主函数
int main() {
struct ListNode *head = createNode(5);
head->next = createNode(2);
head->next->next = createNode(8);
head->next->next->next = createNode(1);
printf("Original list: ");
printList(head);
bubbleSort(head);
printf("Sorted list: ");
printList(head);
return 0;
}
2.2 选择排序
选择排序是一种简单直观的排序算法。它的工作原理是:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
2.2.1 选择排序算法步骤
- 遍历整个链表,找到最小(大)值。
- 将最小(大)值与链表头部节点交换。
- 将剩余链表视为新的未排序链表,重复步骤1和2,直到链表排序完成。
2.2.2 选择排序代码示例
// 选择排序
void selectionSort(struct ListNode *head) {
if (head == NULL || head->next == NULL) {
return;
}
struct ListNode *i, *j, *minNode, *temp;
for (i = head; i != NULL; i = i->next) {
minNode = i;
for (j = i->next; j != NULL; j = j->next) {
if (j->val < minNode->val) {
minNode = j;
}
}
// 交换节点
temp = i->val;
i->val = minNode->val;
minNode->val = temp;
}
}
2.3 插入排序
插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序)。
2.3.1 插入排序算法步骤
- 从第一个元素开始,该元素可以认为已经被排序。
- 取出下一个元素,在已排序的元素序列中从后向前扫描。
- 如果该元素(已排序)大于新元素,将该元素移到下一位置。
- 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置。
- 将新元素插入到该位置后。
- 重复步骤2~5。
2.3.2 插入排序代码示例
// 插入排序
void insertionSort(struct ListNode *head) {
if (head == NULL || head->next == NULL) {
return;
}
struct ListNode *i, *j, *temp;
for (i = head->next; i != NULL; i = i->next) {
temp = i;
j = i->prev;
while (j != NULL && j->val > temp->val) {
j->next = j->next->next;
j->next->prev = j;
j = j->prev;
}
temp->prev = j;
temp->next = j->next;
j->next = temp;
j->next->prev = temp;
}
}
3. 总结
本文介绍了C语言中几种常见的链表排序算法,包括冒泡排序、选择排序和插入排序。通过这些示例,您可以轻松入门链表排序。在实际应用中,您可以根据具体需求选择合适的排序算法,并对代码进行优化和改进。希望本文对您有所帮助!
