c# - 为什么同一设计会得到两种不同的结果？

Question

快速提问:

我有一堆(云)坐标，我倾向于找到整堆坐标的四个角坐标。我所说的角落是指:

MyDesiredResult = { SmallestX, BiggestY, BiggestX, SmallestY }

我使用这个旧例程来获取我的值(value)观，它是正确的:

double smallestX = MyCloud[0].X;       // assing X of first element to my result controller
var tempCoordPoint = MyCloud[0];       // assign first element to my result controller

for (int i = 0; i < MyCloud.Count; i++)
{
    if (smallestX > MyCloud[i].X)      // find minimum X
    {
        smallestX = MyCloud[i].X;
        tempCoordPoint = MyCloud[i];
    }
}

MyResult.Add(tempCoordPoint);           // add to my list

但是，我需要执行四次(对于四个结果)。因此，我尝试通过将其更改为我只使用一次的新例程来优化我的代码:

List<CoordPoint> MySortedList = MyCloud.Select(c => new CoordPoint { X = c.X, Y = c.Y, Z = c.Z, Color = c.Color }).ToList();

MySortedList.Sort((c1, c2) => c1.X.CompareTo(c2.X));     // sort on X
var temp = MySortedList[MySortedList.Count - 1];         // hold biggest X in a temp variable
MyResult.Add(MySortedList[0]);                           // add smallest X to my result

MySortedList.Sort((c1, c2) => c1.Y.CompareTo(c2.Y)); ;   // sort on Y
MyResult.Add(MySortedList[MySortedList.Count - 1]);      // add biggest Y to my result 
MyResult.Add(temp);                                      // add biggest X to my result
MyResult.Add(MySortedList[0]);                           // add smallest Y to my result

但它给出了不同的结果。我想显示示例输入、当前输出和所需的输出。我可以跳过示例输入(巨大的负载)并显示结果。谁能指出我做错了什么？

对于相同的输入:

旧例程的结果:

(0, 4), (15, 12), (23, 6), (19, 0)

新例程的结果:

(0, 4), (18, 12), (23, 6), (18, 0)

Answer 1

我会用另一个问题来回答你的问题:

如果两个点具有相同的 Y 坐标，并且该 Y 坐标恰好是最小值或最大值，会发生什么情况？ X 坐标也是如此吗？

让我用一个例子来说明。假设您有以下 4 点:

(0, 0), (1, 0), (0, 1), (1, 1)

您的原始算法将返回:

(0, 0), (0, 1), (1, 0), (0, 0)

现在假设我们取出了最初的 4 个点并对其进行了洗牌:

(1, 1), (0, 1), (1, 0), (0, 0)

如果您对此运行原始算法，您将得到以下结果:

(0, 1), (1, 1), (1, 1), (1, 0)

根据您的说法，原始算法是正确的，但我只是以两种不同的顺序给出了相同的点集，并得到了两个不同的答案。那么哪个答案是正确的呢？实际的预期结果是什么？

现在，我没有提供您的新算法的结果是有原因的，因为我不知道您的新算法会产生什么结果。我不知道的原因是List<T>.Sort执行不稳定的排序。这意味着比较“相等”的两个元素不一定会按顺序排列。所以，如果我们的输入是 (0, 0), (1, 0), (0, 1), (1, 1)尝试按 X 坐标排序后，以下所有可能性都是有效的:

(0, 0), (0, 1), (1, 0), (1, 1)

(0, 1), (0, 0), (1, 0), (1, 1)

(0, 1), (0, 0), (1, 1), (1, 0)

(0, 0), (0, 1), (1, 1), (1, 0)

List<T>.Sort可以产生其中任何一个。如果您有更多重复的 X 坐标，您将有更多可能的排序。之所以称为不稳定，是因为两个相等元素(例如 (0, 0) 和 (0, 1) )的相对顺序在排序后不会保留。排序算法可能会交换它们的位置。