首页 > 代码库 > 链表插入排序、链表归并排序
链表插入排序、链表归并排序
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 = http://www.mamicode.com/data;>输出链表：
/* * 输出链表结点值。 */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 =http://www.mamicode.com/ 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 =http://www.mamicode.com/ 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;}
链表归并排序
参考：
用归并排序对链表进行排序
<面试题>链表排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。