如何将合并排序算法应用于 C# 中的"List<IntPoint>"？

Question

我有一个代码的合并算法，但代码是为数组编写的所有时间。如何使用

的合并算法?List<IntPoint>(我不想把值放在List<IntPoint>数组不浪费时间)?

代码如下:

class MergeSort
{
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using AForge;
namespace blobdnm
{
class MergeSort
{
private int arraySize;
private List<IntPoint> array;
//takes in array and area of the array that is populated
public PointComparer(List<IntPoint> array, int length)//in here the error is:Non-invocable member 'MergeSort.PointComparer' cannot be used like a method.
{
this.arraySize = length;
this.array = array;
//mergesort is called from the constructor
MergeSort_Recursive(this.array, 0, arraySize - 1);
}
public void DoMerge(List<IntPoint> numbers, int left, int mid, int right)
{
List<IntPoint> temp = new IntPoint[arraySize];//Can not implicitly convert type...
int i, left_end, num_elements, tmp_pos;
left_end = (mid - 1);
tmp_pos = left;
num_elements = (right - left + 1);
while ((left <= left_end) && (mid <= right))
{
if (numbers[left].Compare(numbers[mid]) <= 0)
temp[tmp_pos++] = numbers[left++];
else
temp[tmp_pos++] = numbers[mid++];
}
while (left <= left_end)
temp[tmp_pos++] = numbers[left++];
while (mid <= right)
temp[tmp_pos++] = numbers[mid++];
for (i = 0; i < num_elements; i++)
{
numbers[right] = temp[right];
right--;
}
}
public class PointComparer : IComparer<IntPoint>
{
public static readonly PointComparer Instance = new PointComparer();
public int Compare(IntPoint a, IntPoint b)//int point does not contain a definition for "Compare"...
{
var c = a.X.CompareTo(b.X);
if (c == 0) return a.Y.CompareTo(b.Y);
return c;
}
}
}
}

Answer 1

如果你想排序点，你应该开始使用内置排序，即List<T>.Sort。为此，您可能需要一个自定义比较器:

public class PointComparer : IComparer<IntPoint>
{
public static readonly PointComparer Instance = new PointComparer();
public int Compare(IntPoint a, IntPoint b)
{
var c = a.X.CompareTo(b.X);
if (c == 0) return a.Y.CompareTo(b.Y);
return c;
}
}
...
myPoints.Sort(PointComparer.Instance);

这将可能比任何自定义排序更快，因为它是由熟悉CLR和优化的专业人员编写的。

但是当处理2D数据时，在单一维度中对数据进行排序通常是相当有限的。通常使用某种空间数据结构(如kd树或四叉树)会更好。但这是一个更大的变化，需要你的算法支持这样的结构。

每当我们讨论性能时，重要的一点是测量。也就是说，你应该使用分析器来检查最慢的操作在哪里，看看你是否可以改进它们。像在列表和数组之间复制点这样的操作通常不应该花费太多时间，而且优化已经很快的东西也没有意义。当事情"缓慢"时，一个常见的原因是不必要地重新计算了一些东西，通常是因为开发人员没有意识到，或者不关心，代码是低效的。

在最后一点，我会考虑切换库。AForge已经很老了，我认为它已经不再被维护了。我已经使用MiConvexHull来计算凸壳，它似乎工作得很好。但你可能想访问https://softwarerecs.stackexchange.com/获得推荐。