C语言链表数据排序详解：插入排序、冒泡排序与归并排序
创作时间:
作者:
@小白创作中心
C语言链表数据排序详解：插入排序、冒泡排序与归并排序
引用
1
来源
1.
https://docs.pingcode.com/baike/1035901
在C语言中，链表是一种常用的数据结构，而链表中的数据排序是链表操作中的一个重要环节。本文将详细介绍三种常见的链表排序方法：插入排序、冒泡排序和归并排序，并通过代码示例帮助读者更好地理解这些算法的实现过程。
在C语言中，链表中的数据排序主要有三种常见的方法：插入排序、冒泡排序、归并排序。这些排序算法各有优劣，具体选择哪种方法取决于链表的大小和复杂性。下面将详细介绍这三种排序方法，并给出每种方法的实现步骤和代码示例。
一、插入排序
1、插入排序的概念
插入排序是一种简单直观的排序算法，适用于小规模数据。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
2、实现步骤
- 定义一个新的链表，用于存储排序后的节点。
- 遍历原链表，将每个节点插入到新链表的适当位置。
- 返回新链表的头节点。
3、代码示例
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点
struct Node {
int data;
struct Node* next;
};
// 插入排序的实现
struct Node* insertionSort(struct Node* head) {
if (head == NULL || head->next == NULL) return head;
struct Node* sorted = NULL;
struct Node* current = head;
while (current != NULL) {
struct Node* next = current->next;
if (sorted == NULL || sorted->data >= current->data) {
current->next = sorted;
sorted = current;
} else {
struct Node* temp = sorted;
while (temp->next != NULL && temp->next->data < current->data) {
temp = temp->next;
}
current->next = temp->next;
temp->next = current;
}
current = next;
}
return sorted;
}
// 打印链表
void printList(struct Node* head) {
while (head != NULL) {
printf("%d -> ", head->data);
head = head->next;
}
printf("NULL\n");
}
// 创建新节点
struct Node* newNode(int data) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->next = NULL;
return node;
}
// 主函数
int main() {
struct Node* head = newNode(4);
head->next = newNode(3);
head->next->next = newNode(1);
head->next->next->next = newNode(2);
printf("Original list: \n");
printList(head);
head = insertionSort(head);
printf("Sorted list: \n");
printList(head);
return 0;
}
二、冒泡排序
1、冒泡排序的概念
冒泡排序是一种简单的排序算法。它反复地走访过要排序的链表，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访链表的工作是重复地进行直到没有再需要交换。
2、实现步骤
- 初始化一个标志变量，用于检测是否发生交换。
- 遍历链表，如果当前节点的值大于下一个节点的值，则交换它们。
- 重复步骤2，直到没有发生交换为止。
3、代码示例
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点
struct Node {
int data;
struct Node* next;
};
// 交换两个节点的值
void swap(struct Node* a, struct Node* b) {
int temp = a->data;
a->data = b->data;
b->data = temp;
}
// 冒泡排序的实现
void bubbleSort(struct Node* head) {
if (head == NULL) return;
int swapped;
struct Node *ptr1;
struct Node *lptr = NULL;
do {
swapped = 0;
ptr1 = head;
while (ptr1->next != lptr) {
if (ptr1->data > ptr1->next->data) {
swap(ptr1, ptr1->next);
swapped = 1;
}
ptr1 = ptr1->next;
}
lptr = ptr1;
} while (swapped);
}
// 打印链表
void printList(struct Node* head) {
while (head != NULL) {
printf("%d -> ", head->data);
head = head->next;
}
printf("NULL\n");
}
// 创建新节点
struct Node* newNode(int data) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->next = NULL;
return node;
}
// 主函数
int main() {
struct Node* head = newNode(4);
head->next = newNode(3);
head->next->next = newNode(1);
head->next->next->next = newNode(2);
printf("Original list: \n");
printList(head);
bubbleSort(head);
printf("Sorted list: \n");
printList(head);
return 0;
}
三、归并排序
1、归并排序的概念
归并排序是一种有效的、稳定的、采用分治法的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序将链表分成若干子链表，分别进行排序，然后将有序子链表合并，最终得到有序的链表。
2、实现步骤
- 将链表分成两个子链表。
- 对两个子链表分别进行排序。
- 合并两个有序的子链表。
3、代码示例
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点
struct Node {
int data;
struct Node* next;
};
// 合并两个有序链表
struct Node* sortedMerge(struct Node* a, struct Node* b) {
struct Node* result = NULL;
if (a == NULL)
return b;
else if (b == NULL)
return a;
if (a->data <= b->data) {
result = a;
result->next = sortedMerge(a->next, b);
} else {
result = b;
result->next = sortedMerge(a, b->next);
}
return result;
}
// 分割链表
void frontBackSplit(struct Node* source, struct Node frontRef, struct Node backRef) {
struct Node* fast;
struct Node* slow;
slow = source;
fast = source->next;
while (fast != NULL) {
fast = fast->next;
if (fast != NULL) {
slow = slow->next;
fast = fast->next;
}
}
*frontRef = source;
*backRef = slow->next;
slow->next = NULL;
}
// 归并排序的实现
void mergeSort(struct Node headRef) {
struct Node* head = *headRef;
struct Node* a;
struct Node* b;
if ((head == NULL) || (head->next == NULL)) {
return;
}
frontBackSplit(head, &a, &b);
mergeSort(&a);
mergeSort(&b);
*headRef = sortedMerge(a, b);
}
// 打印链表
void printList(struct Node* head) {
while (head != NULL) {
printf("%d -> ", head->data);
head = head->next;
}
printf("NULL\n");
}
// 创建新节点
struct Node* newNode(int data) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->next = NULL;
return node;
}
// 主函数
int main() {
struct Node* head = newNode(4);
head->next = newNode(3);
head->next->next = newNode(1);
head->next->next->next = newNode(2);
printf("Original list: \n");
printList(head);
mergeSort(&head);
printf("Sorted list: \n");
printList(head);
return 0;
}
四、链表排序的选择
1、时间复杂度和空间复杂度
- 插入排序的时间复杂度是O(n^2)，在链表较小的情况下，插入排序是比较合适的选择。
- 冒泡排序同样是O(n^2)的时间复杂度，适用于较小规模的数据。
- 归并排序的时间复杂度是O(n log n)，适用于大规模数据的排序，但其空间复杂度较高。
2、稳定性和适用场景
- 归并排序是一种稳定的排序算法，而插入排序和冒泡排序在链表实现中也具有稳定性。
- 对于小规模数据，插入排序和冒泡排序是不错的选择；对于大规模数据，归并排序更加高效。
3、代码实现的复杂度
- 归并排序的实现相对复杂，需要分割链表和合并有序链表。
- 而插入排序和冒泡排序的实现较为简单，适合初学者使用。
五、相关问答FAQs：
1. 如何使用C语言对链表中的数据进行排序？
要对链表中的数据进行排序，可以使用常见的排序算法，如冒泡排序、插入排序、选择排序等。具体步骤如下：
- 遍历链表，将链表中的数据存储到数组中。
- 使用所选的排序算法对数组进行排序。
- 将排序后的数组中的数据重新写回链表。
2. 在C语言中，如何实现链表的排序功能？
链表的排序功能可以通过以下步骤实现：
- 遍历链表，找到链表中的最小节点。
- 将最小节点从链表中移除，并将其插入到新链表的末尾。
- 重复上述步骤，直到原链表为空。
- 新链表中的节点顺序即为排序后的结果。
3. 如何在C语言中使用快速排序算法对链表中的数据进行排序？
快速排序是一种高效的排序算法，也可以用于链表排序。以下是使用快速排序对链表进行排序的步骤：
- 选择链表中的一个节点作为基准点。
- 将链表划分为两个部分，一个部分包含小于基准点的节点，另一个部分包含大于基准点的节点。
- 分别对两个部分递归地进行快速排序。
- 将排序好的两个部分连接起来，得到最终的排序链表。
希望以上内容能够解答您对C语言链表中数据排序的疑问。如果您还有其他问题，欢迎随时提问。
热门推荐
电瓶车充电起火致24辆车被烧，法院判销售商赔偿
FPV穿越机：探索飞行新体验的利器
八国联军侵华战争中，为什么美国却始终没有表现出过强的积极性
iNKT细胞疗法新突破：激活免疫系统，抑制胰腺癌肝转移
单考单招落榜了应该怎么办?有什么出路？
红枣功效+禁忌！红枣怎么吃？解析红枣一天吃几颗、哪些人不适合？
桂花树果子有什么用途和功效？
呼吸衰竭最新治疗指南，一文读懂
潜行者2切尔诺贝利之心发售在即 stalker2PC配置大公开
《我的世界大电影》烂番茄新鲜度53% 充满想象力还是愚蠢至极？
清鼻涕黄鼻涕一起流怎么回事
奈良和京都的完整指南！歷史與自然奇觀之旅
孩子有夜磨牙该怎么办
徒步108里缅怀先烈：宁夏两所中学29年坚持的特殊思政课
咖啡过滤纸：选择、使用和影响咖啡品质的要素
如何挑选合适的咖啡滤纸
面料成分：根据标签选择和护理衣服
出口美国必看：完整指南助您顺利通关
深入探讨职业胜任力测评：提升职场竞争力的关键
世界最受欢迎旅游国排名，中国入榜前十
激光投影仪电路板与LED投影仪电路板的性能区别？
西安交大研究生支教团：为孩子打开一扇窗
洪秀全的太平天国：农民起义的领袖
告别扎手指！上海瑞金医院开发无创血糖检测技术
觉悟之道：如何在生活中实现自我超越
970显卡声音大怎么办？全面解决方案与预防措施
申请美国签证免面谈是不是必须要选广州使馆？
Excel透视表制作指南：从入门到精通
黄河治理的中国决心
哪里可以找到电气自动化的培训课程？