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 <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个数以创建链表：
"）;head = CreatLink（TOTAL）;head = LinkInsertSort（head）;printf（"排序后：
"）;PrintLink（head）;putchar（"
"）;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;elsep->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个数以创建链表：
"）;head = CreatLink（TOTAL）;head = LinkMergeSort（head）;printf（"排序后：
"）;PrintLink（head）;putchar（"
"）;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;elsep->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;}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持脚本之家。