C#，单向链表（Simply Linked List）的归并排序（Merge Sort）算法与源代码

单向链表

单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始；链表是使用指针进行构造的列表；又称为结点列表，因为链表是由一个个结点组装起来的；其中每个结点都有指针成员变量指向列表中的下一个结点；
链表是由结点构成，head指针指向第一个成为表头结点，而终止于最后一个指向NULL的指针。

相比较普通的线性结构，链表结构的可以总结一下：
（1）单个结点创建非常方便，普通的线性内存通常在创建的时候就需要设定数据的大小；
（2）结点的删除非常方便，不需要像线性结构那样移动剩下的数据；
（3）结点的访问方便，可以通过循环或者递归的方法访问到任意数据，但是平均的访问效率低于线性表；

归并排序法

归并排序法（Merge Sort，以下简称MS）是分治法思想运用的一个典范。

其主要算法操作可以分为以下步骤：
Step 1：将n个元素分成两个含n/2元素的子序列
Step 2：用MS将两个子序列递归排序（最后可以将整个原序列分解成n个子序列）
Step 3：合并两个已排序好的序列
易知，MS的关键在于Merge过程。对于这一过程的理解，算法导论中给出了一个形象的模型。
即假设桌面上有两堆已排序好的的牌，且每一堆都正面朝下放置。然后我们分别从两堆牌中选取顶上的一张牌（选取之后，堆顶端又会露出新的顶牌），选取较小的一张，放入输出堆，另一张放回。
重复这一步骤，最后直到一堆牌为空。由于两堆牌都是已排序，所以可知，只要将剩下的那堆牌盖到输出堆即完成整个排序过程。

 源程序：

using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;

namespace Legalsoft.Truffer.Algorithm
{
	/// <summary>
	/// 适用于单向列表的归并排序算法
	/// </summary>
	public partial class LinkedList
	{
		#region 算法1
		public LinkNode Merge_Utlility(LinkNode a, LinkNode b)
		{
			if (a == null)
			{
				return b;
			}
			if (b == null)
			{
				return a;
			}
			LinkNode result;
			if (a.Data <= b.Data)
			{
				result = a;
				result.Next = Merge_Utlility(a.Next, b);
			}
			else
			{
				result = b;
				result.Next = Merge_Utlility(a, b.Next);
			}
			return result;
		}

		public LinkNode Merge_Sort(LinkNode h)
		{
			if (h == null || h.Next == null)
			{
				return h;
			}

			LinkNode middle = Tortoise_And_Hare(h);
			LinkNode nextofmiddle = middle.Next;

			middle.Next = null;

			LinkNode left = Merge_Sort(h);

			LinkNode right = Merge_Sort(nextofmiddle);

			LinkNode sortedlist = Merge_Utlility(left, right);
			return sortedlist;
		}

		private LinkNode Tortoise_And_Hare(LinkNode h)
		{
			if (h == null)
			{
				return h;
			}
			LinkNode fastptr = h.Next;
			LinkNode slowptr = h;

			while (fastptr != null)
			{
				fastptr = fastptr.Next;
				if (fastptr != null)
				{
					slowptr = slowptr.Next;
					fastptr = fastptr.Next;
				}
			}
			return slowptr;
		}

		public LinkNode Push(LinkNode head, int d)
		{
			LinkNode node = new LinkNode(d);
			node.Next = head;
			head = node;
			return head;
		}
		#endregion

		#region 算法2
		static LinkNode Merge_Sort_Second(LinkNode head)
		{
			if (head.Next == null)
			{
				return head;
			}
			LinkNode mid = Tortoise_And_Hare_Second(head);
			LinkNode head2 = mid.Next;
			mid.Next = null;
			LinkNode newHead1 = Merge_Sort_Second(head);
			LinkNode newHead2 = Merge_Sort_Second(head2);
			LinkNode finalHead = Merge_Utility_Second(newHead1, newHead2);

			return finalHead;
		}

		private static LinkNode Merge_Utility_Second(LinkNode a, LinkNode b)
		{
			LinkNode merged = new LinkNode(Int32.MinValue);
			LinkNode temp = merged;

			while (a != null && b != null)
			{
				if (a.Data < b.Data)
				{
					temp.Next = a;
					a = a.Next;
				}
				else
				{
					temp.Next = b;
					b = b.Next;
				}
				temp = temp.Next;
			}

			while (a != null)
			{
				temp.Next = a;
				a = a.Next;
				temp = temp.Next;
			}

			while (b != null)
			{
				temp.Next = b;
				b = b.Next;
				temp = temp.Next;
			}
			return merged.Next;
		}

		static LinkNode Tortoise_And_Hare_Second(LinkNode head)
		{
			LinkNode slow = head;
			LinkNode fast = head.Next;
			while (fast != null && fast.Next != null)
			{
				slow = slow.Next;
				fast = fast.Next.Next;
			}
			return slow;
		}
		#endregion

		public static List<int> ToList(LinkNode head)
		{
			List<int> list = new List<int>();
			while (head != null)
			{
				list.Add(head.Data);
				head = head.Next;
			}
			return list;
		}

		public static string ToHtml(LinkNode head, LinkNode cur)
		{
			StringBuilder sb = new StringBuilder();
			sb.AppendLine("<style>");
			sb.AppendLine(".node { float:left;width:45px;height:45px;line-height:45px;font-size:21px;text-align:center;border:solid 1px #DD0000; }");
			sb.AppendLine(".node_cur { float:left;width:45px;height:45px;line-height:45px;font-size:21px;font-weight:bold;text-align:center;border:solid 1px #FF6701;background-color:#FAFA90; }");
			sb.AppendLine(".link { float:left;width:45px;height:45px;line-height:45px;font-size:12px;text-align:center;border:solid 0px #DD0000;white-space:nowrap;word-break:keep-all; }");
			sb.AppendLine("</style>");
			while (head != null)
			{
				if (head == cur)
				{
					sb.AppendLine("<div class='node_cur'>" + head.Data + "</div>");
				}
				else
				{
					sb.AppendLine("<div class='node'>" + head.Data + "</div>");
				}
				if(head.Next !=null)
                {
					sb.AppendLine("<div class='link'>--&gt;</div>");
				}
				head = head.Next;
			}
			return sb.ToString();
		}
	}
}

节点信息： 

	public class LinkNode
	{
		public int Data { get; set; } = 0;
		public LinkNode Next { get; set; } = null;
		public LinkNode(int d)
		{
			this.Data = d;
		}
	}

POWER BY 315SOFT.COM