本篇文章详细的介绍了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 <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 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;
}
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。
免责声明：本站文章均来自网站采集或用户投稿，网站不提供任何软件下载或自行开发的软件！
如有用户或公司发现本站内容信息存在侵权行为，请邮件告知！ 858582#qq.com
暂无“JavaScript实现链表插入排序和链表归并排序”评论...
《魔兽世界》大逃杀！60人新游玩模式《强袭风暴》3月21日上线
暴雪近日发布了《魔兽世界》10.2.6 更新内容，新游玩模式《强袭风暴》即将于3月21 日在亚服上线，届时玩家将前往阿拉希高地展开一场 60 人大逃杀对战。
艾泽拉斯的冒险者已经征服了艾泽拉斯的大地及遥远的彼岸。他们在对抗世界上最致命的敌人时展现出过人的手腕，并且成功阻止终结宇宙等级的威胁。当他们在为即将于《魔兽世界》资料片《地心之战》中来袭的萨拉塔斯势力做战斗准备时，他们还需要在熟悉的阿拉希高地面对一个全新的敌人──那就是彼此。在《巨龙崛起》10.2.6 更新的《强袭风暴》中，玩家将会进入一个全新的海盗主题大逃杀式限时活动，其中包含极高的风险和史诗级的奖励。
《强袭风暴》不是普通的战场，作为一个独立于主游戏之外的活动，玩家可以用大逃杀的风格来体验《魔兽世界》，不分职业、不分装备（除了你在赛局中捡到的），光是技巧和战略的强弱之分就能决定出谁才是能坚持到最后的赢家。本次活动将会开放单人和双人模式，玩家在加入海盗主题的预赛大厅区域前，可以从强袭风暴角色画面新增好友。游玩游戏将可以累计名望轨迹，《巨龙崛起》和《魔兽世界：巫妖王之怒 经典版》的玩家都可以获得奖励。
更新动态
2024年12月29日
2024年12月29日
- 小骆驼-《草原狼2(蓝光CD)》[原抓WAV+CUE]
- 群星《欢迎来到我身边 电影原声专辑》[320K/MP3][105.02MB]
- 群星《欢迎来到我身边 电影原声专辑》[FLAC/分轨][480.9MB]
- 雷婷《梦里蓝天HQⅡ》 2023头版限量编号低速原抓[WAV+CUE][463M]
- 群星《2024好听新歌42》AI调整音效【WAV分轨】
- 王思雨-《思念陪着鸿雁飞》WAV
- 王思雨《喜马拉雅HQ》头版限量编号[WAV+CUE]
- 李健《无时无刻》[WAV+CUE][590M]
- 陈奕迅《酝酿》[WAV分轨][502M]
- 卓依婷《化蝶》2CD[WAV+CUE][1.1G]
- 群星《吉他王(黑胶CD)》[WAV+CUE]
- 齐秦《穿乐(穿越)》[WAV+CUE]
- 发烧珍品《数位CD音响测试-动向效果（九）》【WAV+CUE】
- 邝美云《邝美云精装歌集》[DSF][1.6G]
- 吕方《爱一回伤一回》[WAV+CUE][454M]