数组中.用非平凡比较函数排序

本文关键字：比较 函数 排序 数组 | 更新日期: 2023-09-27 18:11:41

考虑以下来自 c# 5.0的代码， 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排序?

数组中.用非平凡比较函数排序

最有可能的主题是关于Sort不保证元素相等的顺序这一事实。不像稳定排序算法保留相等元素的原始顺序，"不稳定排序"可能交换它们。通常，当你手工排序时，你使用的是"稳定排序"版本。

数组。:

这个实现执行一个不稳定排序;也就是说，如果两个元素相等，它们的顺序可能不会被保留。相反，稳定排序保留相等元素的顺序。

sample中使用的sort函数使得1 == 3, 1 == 5允许以任何方式对这些数字排序，只要它们与其他数字的顺序正确:1,3,5(稳定-与源中的顺序相同)或任何序列3,1,5(不稳定排序)。

。OrderBy实现了"稳定排序"，您可以在下面的示例中看到使用相同比较函数的结果:

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;
    }
}

尽管数组。这种指定

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

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

这个实现执行一个不稳定的sort

，因此，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承诺排序你的序列，但它没有承诺如何做到这一点。

该代码相当于:

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}

总之，似乎"为什么"是因为每个人都说的问题，但我还不完全确定。

在这里你不排序相等的余数如何得到的顺序

试试这个:

Array.Sort(numbers, (x, y) => x % 2 == y % 2 ? x < y ? 1 : -1 : x % 2 == 1 ? -1 : 1);

我的理解是:根据代码，您可以将其更改为:

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;
}

所以易行。sort是根据条件(OnComparison，根据返回值)进行排序，而不是与int[]数字进行比较。所以3 &5,1，都返回-1作为数组的定义。: 

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

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

相关文章：