本篇文章详细的介绍了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.链表归并排序