C语言数据结构链表与归并排序实例详解

2020-01-26 14:16:59

字体：大中小

来源：转载

供稿：网友

C语言数据结构链表与归并排序实例详解

归并排序适合于对链表进行原址排序，即只改变指针的连接方式，不交换链表结点的内容。

归并排序的基本思想是分治法：先把一个链表分割成只有一个节点的链表，然后按照一定顺序、自底向上合并相邻的两个链表。

只要保证各种大小的子链表是有序的，那么最后返回的链表就一定是有序的.

归并排序分为分割和合并两个子过程。分割是用递归的方法，把链表对半分割成两个子链表；合并是在递归返回（回朔）的时候，把两个有序链表合并成一个有序链表。

绘图1

(注意：只有一个节点的链表一定是有序的)

这里sort过程就是分割过程；merge过程就是合并且排序的过程

说到分割链表，那么问题来了：链表不是随机访问的，我怎么知道分割点在哪里？一个宝贵的经验就是：维护两个指针，一快一慢。快指针每次后移两个单位，慢指针每次只移动一个单位。当快指针移动到tail或者最后一个有效节点时，慢指针就指向了中间的节点。

sort过程:

Node* sort (Node* beg){  if(beg==tail || beg->next==tail) return beg;  Node* a = beg; Node* b = beg->next;  while(b!=tail && b->next != tail)  {    a = a->next; b = b->next->next;  }  b = a->next;  //the beginning of right part  a->next = tail; //the end of left part  return merge(sort(beg), sort(b));}

把链表分割之后就要合并。merge操作传入的参数是两个有序链表，返回的是合并后的有序的链表。两个有序链表简单拼接之后不一定是有序的，需要对每一个元素重排。这个重排的过程是从两个链表各自最小（最大）元素开始，谁小（大）就把谁放到新的链表里。

merge1

Node* LinkedList<T>::merge(Node* a, Node* b){	Node dummy = Node();	Node* head = &dummy;	// temp是正在合并的表的节点	Node* temp = head;	while(a!=tail && b!=tail) //逐个比较链表a和链表b的每个元素	{		if(a->data <= b->data)		{			// 如果a比b小, 那么当前结点的后继就是a			temp->next = a;			// 把当前节点移向后继			temp = a;			// a后移			a = a->next;		}		else 		{			temp->next = b;			temp = b; 			b = b->next;		}		// 如果原表a已经排完,那么新表后面就放b的剩余元素		// 否则仍然以a为标准和b进行比较		temp->next = (a==tail) ? b : a;	}	return head->next;}

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

上一篇：C语言 MD5的源码实例详解

下一篇：C语言数据结构之中序二叉树实例详解