Array.Sort in with nontrivial comparison function
在Nutshell中考虑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
?
虽然Array.Sort指定
如果分区大小少于16个元素,则使用插入排序算法。
它没有指定它如何进行此插入排序或它使用的插入排序的风格。 如前所述,它还指定了
此实现执行不稳定的排序
因此, Array.Sort
承诺返回后唯一的元素顺序是它们被排序。 这适用于{3, 5, 1, 2, 4}
。
考虑到Array.Sort
使用的算法甚至可以做这样的事情(Pseudocode):
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
完成的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
承诺对序列进行排序,但它不承诺如何执行此操作。
最有可能的主题是Sort
不保证相等元素的顺序。 与保持相等元素的原始顺序的稳定排序算法不同,“不稳定排序”可以交换它们。 通常,当您手动排序时,您会执行“稳定排序”版本。
Array.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 { public int Compare( int x, int y) { return x % 2 == y % 2 ? 0 : 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; }
我明白了:
{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问题,但我还不完全确定。
在这里,你不是排序等同于你如何得到秩序
试试这个:
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; }
所以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}
上述就是C#学习教程:Array.Sort in with nontrivial comparison function分享的全部内容,如果对大家有所用处且需要了解更多关于C#学习教程,希望大家多多关注---计算机技术网(www.ctvol.com)!
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/cdevelopment/961044.html