以面向对象的方式开发的归并排序算法

• 下载 MergeSort.zip - 41.7 KB

引言

在本文中，我将向您展示我个人使用 C# 实现的归并排序算法。此实现的**目的**不在于找到实现著名算法的最快方法（您可以通过快速搜索轻松找到数十种实现）。其目的是创建并分享一个基于类和对象的实现，试图组织和解耦通常完全写在一个难以阅读的大方法中的代码。我故意没有使用 .NET 库中的任何函数或对象，因为我想尽可能地保持解决方案的“平台独立性”。

在我的方法中，我将尝试划分职责，将其放入不同的类中，并编写（希望如此）“清晰的代码”。尽管如此，我还是会用一个我创建的小型测试套件来支持我的实现，以便通过 TDD 方法开发该算法。

本文的目的不是教您任何东西，而是与您分享我的成果，收集尽可能多的建议和改进，因此请随时提出您的意见。

原始的归并排序算法

下面是摘自维基百科的归并排序算法的描述。从概念上讲，该算法从一个未排序的列表开始，并按以下方式工作：

1. 将未排序的列表分成 n 个子列表，每个子列表包含一个元素（一个元素的列表被认为是已排序的）。
2. 重复合并子列表，生成新的子列表，直到只剩下一个子列表。（这将是已排序的列表。）

通常实现该算法所需的伪代码包含这两个函数：

• merge_sort 函数
• Merge 函数

它看起来是这样的（来自维基百科）：

function merge_sort(list m)
    // if list size is 1, consider it sorted and return it
    if length(m) <= 1
        return m
    // else list size is > 1, so split the list into two sublists
    var list left, right
    var integer middle = length(m) / 2
    for each x in m before middle
         add x to left
    for each x in m after or equal middle
         add x to right
    // recursively call merge_sort() to further split each sublist
    // until sublist size is 1
    left = merge_sort(left)
    right = merge_sort(right)
    // merge the sublists returned from prior calls to merge_sort()
    // and return the resulting merged sublist
    return merge(left, right)

function merge(left, right)
    var list result
    while length(left) > 0 or length(right) > 0
        if length(left) > 0 and length(right) > 0
            if first(left) <= first(right)
                append first(left) to result
                left = rest(left)
            else
                append first(right) to result
                right = rest(right)
        else if length(left) > 0
            append first(left) to result
            left = rest(left)
        else if length(right) > 0
            append first(right) to result
            right = rest(right)
    end while
    return result

嗯……这个伪代码版本似乎在同一个函数中做了很多事情：检查数组长度、比较数字、管理迭代……实际上，对于只有两个函数来说，这太多了。这是如何尝试分解职责的一个很好的例子。我们开始吧。

我的代码是如何工作的

好了，在研究这个归并排序时，我发现了三个主要的职责，它们描述了算法的主要步骤。运行归并排序时，我们总是需要：

• 将原始数组分成小于两个元素的几部分；
• 通过元素比较对分割后的数组进行排序；
• 合并已排序的数组；

对于这些行为，我创建了三个对象，命名为：

• ArraySplitter
• ComparableArray
• Merger

一切都由一个名为“MergeSort”的类驱动，该类以非常简单的方式使用这三个对象，只执行三个操作：

• 拆分数组
• 排序分割后的数组
• 合并数组

因此，如果您查看这个类的代码，您会看到：

public int[] Sort(int[] arrayToSort)
{
    if (arrayToSort.Length==1)
        return arrayToSort;

    if (arrayToSort.Length == 2)
    return SortTwoElements(arrayToSort[0], arrayToSort[1]);

    var splitter = new ArraySplitter(arrayToSort);
    int[] splittedArrayA = splitter.GetFirstPart();
    int[] splittedArrayB = splitter.GetSecondPart();
            
    int[] sortedArrayA = Sort(splittedArrayA);
    int[] sortedArrayB = Sort(splittedArrayB);

    var merger = new Merger();
    return merger.Merge(sortedArrayA,sortedArrayB);
}

private int[] SortTwoElements(int firstElement, int secondElement)
{
    var min = (Math.Abs(firstElement + secondElement) - Math.Abs(firstElement - secondElement)) / 2;
    var max = (Math.Abs(firstElement + secondElement) + Math.Abs(firstElement - secondElement)) / 2;
    return new[] { min, max };
}

最后，现在，我们可以理解谁在做什么，因为在这个层面，我们看不到所有的“技术细节”，或者更好的是，我们**不**想看到事情**如何**完成，因为这是我们想委托给内部类的事情。

在这个层面，我们只想看到算法执行三个主要步骤：

1. 拆分
2. Sort
3. 合并

代码详解

ArraySplitter

这个类允许您将数组拆分成两部分。当数组的维度是奇数时需要特殊处理。

public class ArraySplitter
{
    private readonly int[] _arrayToSort;
    private readonly int[] _firstPart;
    private readonly int[] _secondPart;

    public ArraySplitter(int[] arrayToSort)
    {
        _arrayToSort = arrayToSort;
        _firstPart = new int[_arrayToSort.Length / 2];
        _secondPart = new int[_arrayToSort.Length - _firstPart.Length];
    }

    public int[] GetFirstPart()
    {
        for (int i = 0; i < (_arrayToSort.Length / 2); i++)
            _firstPart[i] = _arrayToSort[i];

        return _firstPart;
    }

    public int[] GetSecondPart()
    {
        for (int i = 0; i < _arrayToSort.Length - (_arrayToSort.Length / 2); i++)
            _secondPart[i] = _arrayToSort[_firstPart.Length + i];
        
        return _secondPart;
    }
}

Merger

这个类能够合并两个已排序的数组，并返回一个保持元素排序的新数组。这个数组是通过始终取出两个数组中最小的元素来构建的，与这个类相关的唯一职责是**合并**元素。决定哪个元素是最小的职责被委托给了“ComparableArray”对象（见下文）。

public class Merger
{
    public int[] Merge(int[] sortedArrayA, int[] sortedArrayB)
    {
        var mergedArray = new int[sortedArrayA.Length + sortedArrayB.Length];
        var visitableArrayA = new ComparableArray(sortedArrayB);
        var visitableArrayB = new ComparableArray(sortedArrayA);

        for (int i = 0; i < mergedArray.Length; i++)
            mergedArray[i] = visitableArrayB.GetNextSmallerElement(visitableArrayA);
        
        return mergedArray;
    }
}

ComparableArray

这是一个“特殊的”数组，它内部包含逻辑，可以检索下一个最小的元素，并将其与类似的其他数组进行比较。也许这个名字不是最好的选择……

无论如何，这个数组会一直保持一个“窗口”，始终对下一个要比较的元素保持开放。所有通过数组元素移动并比较新元素（如果前一个已经被取出）所需的逻辑都封装在这个数组内部。代码需要考虑数组比被比较的数组大（或小）的情况。在下面的代码片段中，我将展示处理这种情况的小段代码，但您可以查看完整的实现，进入代码。

public class ComparableArray
{
    ...

    public int GetNextSmallerElement(ComparableArray arrayToCompare)
    {
        if (CanPickNext)
        {
            if (arrayToCompare.CanPickNext)
            {
                if (Current < arrayToCompare.Current)
                    return GetAndMove();
                else
                    return arrayToCompare.GetAndMove();
            }
            return GetAndMove();
        }

        return arrayToCompare.GetAndMove();
    }

    ...
}

历史

• 2012-07-17：文章的第一个版本。
• 2012-07-18：增强了对代码工作原理的描述。
• 2012-08-16：包含了一个“SortTwoElements”方法的新实现，现在可以在不使用 IF 比较的情况下对元素进行排序。这个实现由 G.Giordano 提供，我希望感谢他的建议。
• 2012-11-14：“SortTwoElements”方法的实现现在已显示在“我的代码如何工作”部分的代码片段中。