本篇文章詳細的介紹了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;}以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持武林網。
新聞熱點
疑難解答
