C# 链表排序之归并排序

在C#中，对链表进行归并排序是一个有效的选择，特别是当链表可能包含大量元素时。归并排序是一种分治算法，它将链表分成两半，对每半部分进行递归排序，然后将排序后的两部分合并成一个有序链表。

下面是一个C#中使用LinkedList<T>进行归并排序的示例代码：

using System;
using System.Collections.Generic;public class Program
{public static void Main(string[] args){LinkedList<int> linkedList = new LinkedList<int>();// 添加一些未排序的元素到链表中linkedList.AddLast(4);linkedList.AddLast(1);linkedList.AddLast(3);linkedList.AddLast(5);linkedList.AddLast(2);Console.WriteLine("原始链表:");PrintLinkedList(linkedList);// 对链表进行归并排序linkedList = MergeSort(linkedList);Console.WriteLine("排序后的链表:");PrintLinkedList(linkedList);}// 归并排序函数static LinkedList<int> MergeSort(LinkedList<int> list){if (list.Count <= 1){// 如果链表为空或只有一个元素，则直接返回return list;}// 分割链表var middle = list.Count / 2;var firstHalf = new LinkedList<int>();var secondHalf = new LinkedList<int>();var currentNode = list.First;for (int i = 0; i < middle; i++){firstHalf.AddLast(currentNode.Value);currentNode = currentNode.Next;}while (currentNode != null){secondHalf.AddLast(currentNode.Value);currentNode = currentNode.Next;}// 递归排序两半firstHalf = MergeSort(firstHalf);secondHalf = MergeSort(secondHalf);// 合并两半return Merge(firstHalf, secondHalf);}// 合并两个已排序的链表static LinkedList<int> Merge(LinkedList<int> list1, LinkedList<int> list2){var mergedList = new LinkedList<int>();var node1 = list1.First;var node2 = list2.First;while (node1 != null && node2 != null){if (node1.Value < node2.Value){mergedList.AddLast(node1.Value);node1 = node1.Next;}else{mergedList.AddLast(node2.Value);node2 = node2.Next;}}// 如果list1还有剩余元素，将它们添加到mergedList中while (node1 != null){mergedList.AddLast(node1.Value);node1 = node1.Next;}// 如果list2还有剩余元素（理论上不应该，因为它们是等长的或list2更短），也添加到mergedList中// 但为了代码的健壮性，还是加上这部分while (node2 != null){mergedList.AddLast(node2.Value);node2 = node2.Next;}return mergedList;}// 打印链表static void PrintLinkedList(LinkedList<int> list){foreach (var item in list){Console.Write(item + " ");}Console.WriteLine();}
}

在这个示例中，MergeSort函数是递归的，它将链表分成两半，直到每部分只有一个元素（或为空），然后调用Merge函数来合并这些已排序的部分。Merge函数遍历两个已排序的链表，并将较小的元素依次添加到新的链表中，直到两个链表都被完全遍历。最后，如果某个链表还有剩余的元素，这些元素也会被添加到结果链表中（尽管在归并排序的上下文中，这种情况通常不会发生，因为两个链表在开始时就被设计为等长的，或者其中一个为空）。

请注意，由于链表是单向的，因此在分割链表时，我们需要创建两个新的链表来存储两半的元素。这会导致额外的内存使用，但与数组相比，链表在分割和合并时不需要大量的数据移动操作，因此这种额外内存使用是可以接受的。