ZetCode

C# 归并排序

最后修改于 2025年3月8日

本文探讨了 C# 中的归并排序算法，演示了它在对数字和文本数据进行升序和降序排序中的应用，并与快速排序进行了基准测试。

算法是精心设计的结构化步骤序列，用于高效地解决问题或执行任务。 它是编程的基石，驱动着计算解决方案。

排序意味着将数据组织成特定的顺序，例如升序或降序。 这对于增强各种应用程序中的数据检索和分析至关重要。

常用排序算法

以下是一些著名的排序算法

归并排序算法

归并排序是一种分而治之的算法，它将数组分成两半，递归地对每一半进行排序，然后将它们按排序后的顺序合并在一起。

归并排序具有 O(n log n) 的一致时间复杂度，稳定且高效，尽管它需要额外的空间进行合并。 它在链表和大型数据集方面表现出色。

归并排序示例

以下是使用顶级语句的数字和字符串的 C# 归并排序实现。

MergeSort.cs 
// MergeSort.cs
int[] MergeSort(int[] arr)
{
    if (arr.Length <= 1)
    {
        return arr;
    }

    int mid = arr.Length / 2;
    int[] left = MergeSort(arr[..mid]);
    int[] right = MergeSort(arr[mid..]);
    return Merge(left, right);
}

int[] Merge(int[] left, int[] right)
{
    var result = new List<int>(left.Length + right.Length);
    int i = 0, j = 0;

    for (; i < left.Length && j < right.Length;)
    {
        if (left[i] < right[j])
        {
            result.Add(left[i]);
            i++;
        }
        else
        {
            result.Add(right[j]);
            j++;
        }
    }
    
    result.AddRange(left[i..]);
    result.AddRange(right[j..]);
    return result.ToArray();
}

string[] MergeSortStrings(string[] arr)
{
    if (arr.Length <= 1)
    {
        return arr;
    }

    int mid = arr.Length / 2;
    string[] left = MergeSortStrings(arr[..mid]);
    string[] right = MergeSortStrings(arr[mid..]);
    return MergeStrings(left, right);
}

string[] MergeStrings(string[] left, string[] right)
{
    var result = new List<string>(left.Length + right.Length);
    int i = 0, j = 0;

    for (; i < left.Length && j < right.Length;)
    {
        if (string.Compare(left[i], right[j]) < 0)
        {
            result.Add(left[i]);
            i++;
        }
        else
        {
            result.Add(right[j]);
            j++;
        }
    }
    result.AddRange(left[i..]);
    result.AddRange(right[j..]);
    return result.ToArray();
}

int[] SortDescending(int[] arr)
{
    int[] sorted = MergeSort(arr);

    for (int i = 0, j = sorted.Length - 1; i < j; i++, j--)
    {
        (sorted[i], sorted[j]) = (sorted[j], sorted[i]);
    }

    return sorted;
}

string[] SortStringsDescending(string[] arr)
{
    string[] sorted = MergeSortStrings(arr);

    for (int i = 0, j = sorted.Length - 1; i < j; i++, j--)
    {
        (sorted[i], sorted[j]) = (sorted[j], sorted[i]);
    }

    return sorted;
}

int[] numbers = [38, 27, 43, 3, 9, 82, 10];
string[] words = ["apple", "banana", "cherry", "date", "elderberry"];
Console.WriteLine("Sorted numbers (ascending): " + string.Join(" ", MergeSort(numbers)));
Console.WriteLine("Sorted numbers (descending): " + string.Join(" ", SortDescending(numbers)));
Console.WriteLine("Sorted words (ascending): " + string.Join(" ", MergeSortStrings(words)));
Console.WriteLine("Sorted words (descending): " + string.Join(" ", SortStringsDescending(words)));

MergeSort 方法递归地分割和合并整数数组，而 MergeSortStrings 对字符串执行相同的操作。 Merge 辅助方法组合排序后的两半。

对于降序，SortDescending 和 SortStringsDescending 反转升序结果。 这种方法利用 C# 的数组操作来实现清晰和效率。

归并排序与快速排序的比较

归并排序保证 O(n log n) 的时间复杂度和稳定性，使其可靠。 快速排序的平均时间复杂度为 O(n log n)，但在最坏情况下（例如排序后的数据）可能会降级为 O(n²)。

此基准测试比较了它们在 C# 中大型数据集上的性能。

Benchmark.cs 
// Benchmark.cs
using System.Diagnostics;

int[] MergeSort(int[] arr)
{
    if (arr.Length <= 1)
    {
        return arr;
    }
    int mid = arr.Length / 2;
    int[] left = MergeSort(arr[..mid]);
    int[] right = MergeSort(arr[mid..]);
    return Merge(left, right);
}

int[] Merge(int[] left, int[] right)
{
    var result = new List<int>(left.Length + right.Length);
    int i = 0, j = 0;
    for (; i < left.Length && j < right.Length;)
    {
        if (left[i] < right[j])
        {
            result.Add(left[i]);
            i++;
        }
        else
        {
            result.Add(right[j]);
            j++;
        }
    }

    result.AddRange(left[i..]);
    result.AddRange(right[j..]);
    return result.ToArray();
}

int[] QuickSort(int[] arr)
{
    if (arr.Length <= 1)
    {
        return arr;
    }

    int pivot = arr[arr.Length / 2];
    var left = new List<int>();
    var middle = new List<int>();
    var right = new List<int>();

    foreach (int x in arr)
    {
        if (x < pivot)
        {
            left.Add(x);
        }
        else if (x == pivot)
        {
            middle.Add(x);
        }
        else
        {
            right.Add(x);
        }
    }

    return [.. QuickSort(left.ToArray()), .. middle, .. QuickSort(right.ToArray())];
}

Random rand = new(Random.Shared.Next());
int[] numbers = new int[10000];
for (int i = 0; i < numbers.Length; i++)
{
    numbers[i] = rand.Next(10000);
}

int[] mergeData = numbers.ToArray();
Stopwatch sw = Stopwatch.StartNew();
MergeSort(mergeData);
double mergeTime = sw.Elapsed.TotalSeconds;

int[] quickData = numbers.ToArray();
sw = Stopwatch.StartNew();
QuickSort(quickData);
double quickTime = sw.Elapsed.TotalSeconds;

Console.WriteLine($"Merge Sort Time: {mergeTime:F6} seconds");
Console.WriteLine($"Quick Sort Time: {quickTime:F6} seconds");

此基准测试在 10,000 个随机整数上测试归并排序和快速排序。 归并排序在合并期间创建新数组，而快速排序以类似的递归方式进行分区。

归并排序的可预测性能与快速排序由于更好的缓存局部性而具有的潜在速度优势形成对比。 实际结果会有所不同，但归并排序可确保一致性。

来源

C# Array.Sort 文档

本教程解释了 C# 中的归并排序，并提供了数字和文本的示例，以及针对快速排序的基准测试。

作者

我叫 Jan Bodnar，我是一位充满热情的程序员，拥有丰富的编程经验。 自 2007 年以来，我一直在撰写编程文章。 迄今为止，我已经撰写了 1,400 多篇文章和 8 本电子书。 我在编程教学方面拥有超过十年的经验。

列出所有 C# 教程。