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个经济体当前指数情况总览
玄武门之变爆发时，李靖在做什么？为何没有参加？
数学归纳法
积分项目管理方法有哪些
只听过二手烟？其实三手烟危害更大！为了家人，速看
手机QQ下载的文件存放在哪里
历史课程中的跨学科教学与学科整合
超然楼—济南的历史文化名楼
随念三宝经：西藏僧众每日必诵的经典
看板上的双面胶如何去除
中风后吞咽困难、喝水咳呛怎么办？专家“六步策略”解燃眉之急
涉春节档电影讨论，600个账号被禁言！是该还电影一个公平真诚的“评论区”
一键开启iPhone App 自动更新功能，让App 永远保持最新版本
股市风向标 | A股成交缩量现象分析
PBL教学法：创新教学模式，打造互动式学习环境！
WWD REVIEW｜年度最值得关注的18篇时尚观察，见证时尚创新的多变与多样
刑事控告，这样梳理证据才规范！
我们的历史，流淌在裕后街的繁华岁月里
吃鱼鳔的好处和坏处
初到佛山，如何租房？租房攻略指南
【储蓄方法】如何储蓄最有效？精选10大无痛快速储蓄攻略
天籁首保需要注意些什么？
流感季，科学使用酒精消杀