6

考虑以下来自C# 5.0 的 Nutshell 中的代码，p。289：

int[] numbers = { 1, 2, 3, 4, 5 };
Array.Sort (numbers, (x, y) => x % 2 == y % 2 ? 0 : x % 2 == 1 ? -1 : 1);

这给出了结果{3, 5, 1, 2, 4}。

我在纸上试了一下，得到了 {1, 3, 5, 2, 4}。

为什么电脑分拣给了3 > 5 > 1？

4

5 回答 5

6

Most likely the topic is about the fact that Sort does not guarantee the order of elements which are equal. Unlike stable sort algorithms that preserve original order of equal elements "unstable sort" may swap them. Normally when you do sorting by hand you do "stable sort" version.

Array.Sort:

This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved. In contrast, a stable sort preserves the order of elements that are equal.

The sort function used in sample makes 1 == 3, 1 == 5 so unstable sort is allowed to order this numbers in any way as long as they are in correct order compared to other ones: 1,3,5 (stable - same order as in source) or any sequence 3,1,5 (unstable sort).

I.e. OrderBy implements "stable sort" and you can see results in following sample using the same compare function:

void Main()
{
    int[] numbers = { 1, 2, 3, 4, 5 };
    var result = numbers.OrderBy(x=> x, new MyComparer()));
      // 1, 3, 5, 2, 4
}

public class MyComparer : IComparer<int>  
{
    public int Compare( int x, int y)
    {
      return  x % 2 == y % 2 ? 0 : x % 2 == 1 ? -1 : 1;
    }
}
于 2013-05-02T06:44:32.797 回答
3

虽然Array.Sort指定

如果分区大小少于 16 个元素，则使用插入排序算法。

它没有具体说明它如何进行这种插入排序或它使用哪种类型的插入排序。如前所述，它还指定

此实现执行不稳定的排序

结果，返回后元素的顺序唯一可以Array.Sort保证的是它们是排序的。对于{3, 5, 1, 2, 4}.

考虑到使用的算法Array.Sort甚至可以做这样的事情（伪代码）：

if sequence = {1, 2, 3, 4, 5} then
    sequence := {3, 5, 1, 2, 4}
end if
Sort(sequence);

当然，这将是实现定义的行为，它可能会在另一个版本的 .NET 框架中发生变化。

将您的代码修改为

Array.Sort(numbers, (x, y) =>
    {
        Console.WriteLine(x + ", " + y);
        return x % 2 == y % 2 ? 0 : x % 2 == 1 ? -1 : 1;
    });

将为您提供由以下人员完成的比较Array.Sort：

1, 3
1, 5
3, 5
1, 3
3, 5
2, 3
3, 4
3, 3
5, 3
5, 3
5, 5
5, 3
2, 4
2, 1
4, 2
1, 4
4, 4
4, 2
1, 2
1, 2
1, 1
1, 2
1, 1

这很可能不是您在纸上进行插入排序的方式。

关键是：Array.Sort承诺对你的序列进行排序，但它不承诺如何做到这一点。

于 2013-05-02T07:22:55.610 回答
2

该代码相当于：

static void Main(string[] args)
{
    int[] numbers = { 1, 2, 3, 4, 5 };
    Array.Sort(numbers, OnComparison); 
}

private static int OnComparison(int x, int y)
{
    if (x%2 == y%2) return 0;
    if (x%2 == 1) return 1;
    return -1;
}

我得到：

{3, 5, 1, 2, 4}

排序操作如下：

0) {1,2,3,4,5}
1) {1,2,3,4,5}
2) {1,2,3,4,5}
3) {1,2,3,4,5}
4) {1,2,3,4,5}
5) {5,2,3,4,1}
6) {5,2,3,4,1}
7) {5,2,3,4,1}
8) {5,3,2,4,1}
9) {5,3,2,4,1}
10) {5,3,2,4,1}
11) {5,3,2,4,1}
12) {3,5,2,4,1}
13) {3,5,2,4,1}
14) {3,5,1,4,2}
15) {3,5,1,4,2}
16) {3,5,1,4,2}
17) {3,5,1,4,2}
18) {3,5,1,2,4}
19) {3,5,1,2,4}
20) {3,5,1,2,4}
21) {3,5,1,2,4}
22) {3,5,1,2,4}
23) Final: {3,5,1,2,4}

所以总而言之，似乎“为什么”是因为每个人都说 0 问题，但我还不确定。

于 2013-05-02T06:48:46.357 回答
1

在这里，您不是按顺序排列的等余数

尝试这个：

Array.Sort(numbers, (x, y) => x % 2 == y % 2 ? x < y ? 1 : -1 : x % 2 == 1 ? -1 : 1);
于 2013-05-02T07:07:54.847 回答
0

这是我的理解方式，基于代码，您可以将其更改为：

static void Main(string[] args)
{
    int[] numbers = { 1, 2, 3, 4, 5 };
    Array.Sort(numbers, OnComparison); 
}

private static int OnComparison(int x, int y)
{
    if (x%2 == y%2) return 0;
    if (x%2 == 1) return -1;
    return 1;
}

所以 arrary.sort 是按条件排序（OnComparison，按返回值），而不是与 int[] 数字进行比较。所以 3 & 5 & 1，都返回为 -1 和 array.sort 的定义：

This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved

这就是为什么，你得到了 {3, 5, 1, 2, 4}

于 2013-05-02T06:59:07.667 回答