JavaScript实现链表插入排序和链表归并排序
本篇文章详细的介绍了JavaScript实现链表插入排序和链表归并排序，链表的归并排序就是对每个部分都进行归并排序，然后合并在一起。
1.链表
1.1链表的存储表示
//链表的存储表示
typedef int ElemType;
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode, *LinkList;登录后复制
1.2基本操作
创建链表：
/*
* 创建链表。
* 形参num为链表的长度，函数返回链表的头指针。
*/
LinkList CreatLink(int num)
{
int i, data;
//p指向当前链表中最后一个结点，q指向准备插入的结点。
LinkList head = NULL, p = NULL, q;
for (i = 0; i < num; i++)
{
scanf("%d", &data);
q = (LinkList)malloc(sizeof(LNode));
q->data = data;
q->next = NULL;
if (i == 0)
{
head = q;
}
else
{
p->next = q;
}
p = q;
}
return head;
}登录后复制
输出链表：
/*
* 输出链表结点值。
*/
int PrintLink(LinkList head)
{
LinkList p;
for (p = head; p ;p = p->next)
{
printf("%-3d ", p->data);
}
return 0;
}登录后复制
2.链表插入排序
基本思想：假设前面n-1个结点有序，将第n个结点插入到前面结点的适当位置，使这n个结点有序。
实现方法：
将链表上第一个结点拆下来，成为含有一个结点的链表(head1)，其余的结点自然成为另外一个链表(head2)，此时head1为含有
一个结点的有序链表；
将链表head2上第一个结点拆下来，插入到链表head1的适当位置，使head1仍有序，此时head1成为含有两个结点的有序链表；
依次从链表head2上拆下一个结点，插入到链表head1中，直到链表head2为空链表为止。最后，链表head1上含所有结点，且结点有序。
插入排序代码：
/*
* 链表插入排序(由小到大)。
* 输入：链表的头指针，
* 输出：排序后链表的头指针。
* 实现方法：将原链表拆成两部分：链表1仍以head为头指针，链表结点有序。链表2以head2为头指针，链表结点无序。
* 将链表2中的结点依次插入到链表1中，并保持链表1有序。
* 最后链表1中包含所有结点，且有序。
*/
LinkList LinkInsertSort(LinkList head)
{
//current指向当前待插入的结点。
LinkList head2, current, p, q;
if (head == NULL)
return head;
//第一次拆分。
head2 = head->next;
head->next = NULL;
while (head2)
{
current = head2;
head2 = head2->next;
//寻找插入位置，插入位置为结点p和q中间。
for (p = NULL, q = head; q && q->data <= current->data; p = q, q = q->next);
if (q == head)
{
//将current插入最前面。
head = current;
}
else
{
p->next = current;
}
current->next = q;
}
return head;
}登录后复制
完整源代码：
/* * 链表插入排序，由小到大 */ #define _CRT_SECURE_NO_WARNINGS #include#include #define TOTAL 10 //链表长度 //链表的存储表示 typedef int ElemType; typedef struct LNode { ElemType data; struct LNode *next; }LNode, *LinkList; LinkList CreatLink(int num); LinkList LinkInsertSort(LinkList head); int PrintLink(LinkList head); /* * 创建链表。 * 形参num为链表的长度，函数返回链表的头指针。 */ LinkList CreatLink(int num) { int i, data; //p指向当前链表中最后一个结点，q指向准备插入的结点。 LinkList head = NULL, p = NULL, q; for (i = 0; i < num; i++) { scanf("%d", &data); q = (LinkList)malloc(sizeof(LNode)); q->data = data; q->next = NULL; if (i == 0) { head = q; } else { p->next = q; } p = q; } return head; } /* * 链表插入排序(由小到大)。 * 输入：链表的头指针， * 输出：排序后链表的头指针。 * 实现方法：将原链表拆成两部分：链表1仍以head为头指针，链表结点有序。链表2以head2为头指针，链表结点无序。 * 将链表2中的结点依次插入到链表1中，并保持链表1有序。 * 最后链表1中包含所有结点，且有序。 */ LinkList LinkInsertSort(LinkList head) { //current指向当前待插入的结点。 LinkList head2, current, p, q; if (head == NULL) return head; //第一次拆分。 head2 = head->next; head->next = NULL; while (head2) { current = head2; head2 = head2->next; //寻找插入位置，插入位置为结点p和q中间。 for (p = NULL, q = head; q && q->data <= current->data; p = q, q = q->next); if (q == head) { //将current插入最前面。 head = current; } else { p->next = current; } current->next = q; } return head; } /* * 输出链表结点值。 */ int PrintLink(LinkList head) { LinkList p; for (p = head; p ;p = p->next) { printf("%-3d ", p->data); } return 0; } int main() { LinkList head; printf("输入Total个数以创建链表：\n"); head = CreatLink(TOTAL); head = LinkInsertSort(head); printf("排序后：\n"); PrintLink(head); putchar('\n'); return 0; }
登录后复制
3.链表归并排序
基本思想：如果链表为空或者含有一个结点，链表自然有序。否则，将链表分成两部分，对每一部分分别进行归并排序，然后将已排序的两个链表归并在一起。
归并排序代码：
/*
* 链表归并排序(由小到大)。
* 输入：链表的头指针，
* 输出：排序后链表的头指针。
* 递归实现方法：将链表head分为两部分，分别进行归并排序，再将排序后的两部分归并在一起。
* 递归结束条件：进行递归排序的链表为空或者只有一个结点。
*/
LinkList LinkMergeSort(LinkList head)
{
LinkList head1, head2;
if (head == NULL || head->next == NULL)
return head;
LinkSplit(head, &head1, &head2);
head1 = LinkMergeSort(head1);
head2 = LinkMergeSort(head2);
head = LinkMerge(head1, head2);
return head;
}登录后复制
其中链表分割函数如下，基本思想是利用slow/fast指针，具体实现方法见注释。
/*
* 链表分割函数。
* 将链表head均分为两部分head1和head2，若链表长度为奇数，多出的结点从属于第一部分。
* 实现方法：首先使指针slow/fast指向链首，
* 然后使fast指针向前移动两个结点的同时，slow指针向前移动一个结点，
* 循环移动，直至fast指针指向链尾。结束时，slow指向链表head1的链尾。
*/
int LinkSplit(LinkList head, LinkList *head1, LinkList *head2)
{
LinkList slow, fast;
if (head == NULL || head->next == NULL)
{
*head1 = head;
*head2 = NULL;
return 0;
}
slow = head;
fast = head->next;
while (fast)
{
fast = fast->next;
if (fast)
{
fast = fast->next;
slow = slow->next;
}
}
*head1 = head;
*head2 = slow->next;
//注意：一定要将链表head1的链尾置空。
slow->next = NULL;
return 0;
}登录后复制
链表归并函数有递归实现和非递归实现两种方法：
非递归实现：
/*
* 链表归并。
* 将两个有序的链表归并在一起，使总链表有序。
* 输入：链表head1和链表head2
* 输出：归并后的链表
* 实现方法：将链表head2中的结点依次插入到链表head1中的适当位置，使head1仍为有序链表。
*/
LinkList LinkMerge(LinkList head1, LinkList head2)
{
LinkList p, q, t;
if (!head1)
return head2;
if (!head2)
return head1;
//循环变量的初始化，q指向链表head1中的当前结点，p为q的前驱。
p = NULL;
q = head1;
while (head2)
{
//t为待插入结点。
t = head2;
head2 = head2->next;
//寻找插入位置，插入位置为p和q之间。
for (;q && q->data <= t->data; p = q, q = q->next);
if (p == NULL)
head1 = t;
else
p->next = t;
t->next = q;
//将结点t插入到p和q之间后，使p重新指向q的前驱。
p = t;
}
return head1;
}登录后复制
递归实现：
LinkList LinkMerge2(LinkList head1, LinkList head2)
{
LinkList result;
if (!head1)
return head2;
if (!head2)
return head1;
if (head1->data <= head2->data)
{
result = head1;
result->next = LinkMerge(head1->next, head2);
}
else
{
result = head2;
result->next = LinkMerge(head1, head2->next);
}
return result;
}登录后复制
完整源代码：
/*
* 链表归并排序，由小到大。
*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define TOTAL 10 //链表长度
//链表的存储表示
typedef int ElemType;
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
LinkList CreatLink(int num);
LinkList LinkMergeSort(LinkList head);
LinkList LinkMerge(LinkList head1, LinkList head2);
LinkList LinkMerge2(LinkList head1, LinkList head2);
int LinkSplit(LinkList head, LinkList *head1, LinkList *head2);
int PrintLink(LinkList head);
/*
* 创建链表。
* 形参num为链表的长度，函数返回链表的头指针。
*/
LinkList CreatLink(int num)
{
int i, data;
//p指向当前链表中最后一个结点，q指向准备插入的结点。
LinkList head = NULL, p = NULL, q;
for (i = 0; i < num; i++)
{
scanf("%d", &data);
q = (LinkList)malloc(sizeof(LNode));
q->data = data;
q->next = NULL;
if (i == 0)
{
head = q;
}
else
{
p->next = q;
}
p = q;
}
return head;
}
/*
* 输出链表结点值。
*/
int PrintLink(LinkList head)
{
LinkList p;
for (p = head; p; p = p->next)
{
printf("%-3d ", p->data);
}
return 0;
}
int main()
{
LinkList head;
printf("输入Total个数以创建链表：\n");
head = CreatLink(TOTAL);
head = LinkMergeSort(head);
printf("排序后：\n");
PrintLink(head);
putchar('\n');
return 0;
}
/*
* 链表归并排序(由小到大)。
* 输入：链表的头指针，
* 输出：排序后链表的头指针。
* 递归实现方法：将链表head分为两部分，分别进行归并排序，再将排序后的两部分归并在一起。
* 递归结束条件：进行递归排序的链表为空或者只有一个结点。
*/
LinkList LinkMergeSort(LinkList head)
{
LinkList head1, head2;
if (head == NULL || head->next == NULL)
return head;
LinkSplit(head, &head1, &head2);
head1 = LinkMergeSort(head1);
head2 = LinkMergeSort(head2);
head = LinkMerge(head1, head2); //非递归实现
//head = LinkMerge2(head1, head2); //递归实现
return head;
}
/*
* 链表归并。
* 将两个有序的链表归并在一起，使总链表有序。
* 输入：链表head1和链表head2
* 输出：归并后的链表
* 实现方法：将链表head2中的结点依次插入到链表head1中的适当位置，使head1仍为有序链表。
*/
LinkList LinkMerge(LinkList head1, LinkList head2)
{
LinkList p, q, t;
if (!head1)
return head2;
if (!head2)
return head1;
//循环变量的初始化，q指向链表head1中的当前结点，p为q的前驱。
p = NULL;
q = head1;
while (head2)
{
//t为待插入结点。
t = head2;
head2 = head2->next;
//寻找插入位置，插入位置为p和q之间。
for (;q && q->data <= t->data; p = q, q = q->next);
if (p == NULL)
head1 = t;
else
p->next = t;
t->next = q;
//将结点t插入到p和q之间后，使p重新指向q的前驱。
p = t;
}
return head1;
}
LinkList LinkMerge2(LinkList head1, LinkList head2)
{
LinkList result;
if (!head1)
return head2;
if (!head2)
return head1;
if (head1->data <= head2->data)
{
result = head1;
result->next = LinkMerge(head1->next, head2);
}
else
{
result = head2;
result->next = LinkMerge(head1, head2->next);
}
return result;
}
/*
* 链表分割函数。
* 将链表head均分为两部分head1和head2，若链表长度为奇数，多出的结点从属于第一部分。
* 实现方法：首先使指针slow/fast指向链首，
* 然后使fast指针向前移动两个结点的同时，slow指针向前移动一个结点，
* 循环移动，直至fast指针指向链尾。结束时，slow指向链表head1的链尾。
*/
int LinkSplit(LinkList head, LinkList *head1, LinkList *head2)
{
LinkList slow, fast;
if (head == NULL || head->next == NULL)
{
*head1 = head;
*head2 = NULL;
return 0;
}
slow = head;
fast = head->next;
while (fast)
{
fast = fast->next;
if (fast)
{
fast = fast->next;
slow = slow->next;
}
}
*head1 = head;
*head2 = slow->next;
//注意：一定要将链表head1的链尾置空。
slow->next = NULL;
return 0;
}登录后复制
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持PHP中文网。
更多JavaScript实现链表插入排序和链表归并排序相关文章请关注PHP中文网！
本站声明
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn
热AI工具
Undresser.AI Undress
人工智能驱动的应用程序，用于创建逼真的裸体照片
AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。
Undress AI Tool
免费脱衣服图片
Clothoff.io
AI脱衣机
Video Face Swap
使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸！
热门文章
如何修复KB5055612无法在Windows 10中安装？
4 周前
By DDD
<🎜>：泡泡胶模拟器无穷大 - 如何获取和使用皇家钥匙
4 周前
By 尊渡假赌尊渡假赌尊渡假赌
<🎜>：种植花园 - 完整的突变指南
3 周前
By DDD
北端：融合系统，解释
4 周前
By 尊渡假赌尊渡假赌尊渡假赌
Mandragora：巫婆树的耳语 - 如何解锁抓钩
3 周前
By 尊渡假赌尊渡假赌尊渡假赌
热工具
记事本++7.3.1
好用且免费的代码编辑器
SublimeText3汉化版
中文版，非常好用
禅工作室 13.0.1
功能强大的PHP集成开发环境
Dreamweaver CS6
视觉化网页开发工具
SublimeText3 Mac版
神级代码编辑软件(SublimeText3)
Python vs. JavaScript：学习曲线和易用性
Apr 16, 2025 am 12:12 AM
Python更适合初学者，学习曲线平缓，语法简洁；JavaScript适合前端开发，学习曲线较陡，语法灵活。1.Python语法直观，适用于数据科学和后端开发。2.JavaScript灵活，广泛用于前端和服务器端编程。
JavaScript和Web：核心功能和用例
Apr 18, 2025 am 12:19 AM
JavaScript在Web开发中的主要用途包括客户端交互、表单验证和异步通信。1)通过DOM操作实现动态内容更新和用户交互；2)在用户提交数据前进行客户端验证，提高用户体验；3)通过AJAX技术实现与服务器的无刷新通信。
JavaScript在行动中：现实世界中的示例和项目
Apr 19, 2025 am 12:13 AM
JavaScript在现实世界中的应用包括前端和后端开发。1)通过构建TODO列表应用展示前端应用，涉及DOM操作和事件处理。2)通过Node.js和Express构建RESTfulAPI展示后端应用。
了解JavaScript引擎：实施详细信息
Apr 17, 2025 am 12:05 AM
理解JavaScript引擎内部工作原理对开发者重要，因为它能帮助编写更高效的代码并理解性能瓶颈和优化策略。1)引擎的工作流程包括解析、编译和执行三个阶段；2)执行过程中，引擎会进行动态优化，如内联缓存和隐藏类；3)最佳实践包括避免全局变量、优化循环、使用const和let，以及避免过度使用闭包。
Python vs. JavaScript：社区，图书馆和资源
Apr 15, 2025 am 12:16 AM
Python和JavaScript在社区、库和资源方面的对比各有优劣。1)Python社区友好，适合初学者，但前端开发资源不如JavaScript丰富。2)Python在数据科学和机器学习库方面强大，JavaScript则在前端开发库和框架上更胜一筹。3)两者的学习资源都丰富，但Python适合从官方文档开始，JavaScript则以MDNWebDocs为佳。选择应基于项目需求和个人兴趣。
Python vs. JavaScript：开发环境和工具
Apr 26, 2025 am 12:09 AM
Python和JavaScript在开发环境上的选择都很重要。1)Python的开发环境包括PyCharm、JupyterNotebook和Anaconda，适合数据科学和快速原型开发。2)JavaScript的开发环境包括Node.js、VSCode和Webpack，适用于前端和后端开发。根据项目需求选择合适的工具可以提高开发效率和项目成功率。
C/C在JavaScript口译员和编译器中的作用
Apr 20, 2025 am 12:01 AM
C和C 在JavaScript引擎中扮演了至关重要的角色，主要用于实现解释器和JIT编译器。 1）C 用于解析JavaScript源码并生成抽象语法树。 2）C 负责生成和执行字节码。 3）C 实现JIT编译器，在运行时优化和编译热点代码，显着提高JavaScript的执行效率。
从网站到应用程序：JavaScript的不同应用
Apr 22, 2025 am 12:02 AM
JavaScript在网站、移动应用、桌面应用和服务器端编程中均有广泛应用。1)在网站开发中，JavaScript与HTML、CSS一起操作DOM，实现动态效果，并支持如jQuery、React等框架。2)通过ReactNative和Ionic，JavaScript用于开发跨平台移动应用。3)Electron框架使JavaScript能构建桌面应用。4)Node.js让JavaScript在服务器端运行，支持高并发请求。
