Array.Sort in with nontrivial comparison function

Question

Hãy xem đoạn mã sau từ C# 5.0 trong Nutshell, tr. 289:

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

cho kết quả {3, 5, 1, 2, 4}.

Tôi đã thử trên giấy và có {1, 3, 5, 2, 4}.

Tại sao phân loại máy tính cho số 3 > 5 > 1?

Answer 1

Mặc dù Array.Sort định

Nếu kích thước phân vùng nhỏ hơn 16 phần tử, nó sử dụng thuật toán sắp xếp chèn.

không xác định cách sắp xếp tính năng chèn này hoặc vị trí chèn mà nó sử dụng. Như đã đề cập, nó bổ sung quy định cụ thể

thi này thực hiện một loại không ổn định

và kết quả là, điều duy nhất Array.Sort lời hứa về thứ tự của các yếu tố sau khi trở về là họ đều được sắp xếp. Điều này đúng cho {3, 5, 1, 2, 4}.

Hãy xem xét rằng các thuật toán được sử dụng bởi Array.Sort sẽ thậm chí được phép làm một cái gì đó như thế này (giả):

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

này, tất nhiên, sẽ thực hiện được xác định hành vi, và nó có thể thay đổi trong một phiên bản khác của Khuôn khổ .NET.

Sửa đổi mã của bạn được

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

sẽ cung cấp cho bạn so sánh được thực hiện bằng cách 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 

Và điều này, rất có khả năng, không phải là cách bạn sẽ làm một sắp xếp chèn vào giấy.

Vấn đề là: Array.Sort hứa hẹn sắp xếp trình tự của bạn nhưng không hứa hẹn cách để thực hiện việc này.

Answer 2

Rất có thể chủ đề là về thực tế là Sort không đảm bảo thứ tự các phần tử bằng nhau. Không giống như các thuật toán stable sort duy trì thứ tự ban đầu của các phần tử bằng nhau "sắp xếp không ổn định" có thể hoán đổi chúng. Thông thường, khi bạn sắp xếp bằng tay, bạn thực hiện phiên bản "sắp xếp ổn định".

Array.Sort:

thi này thực hiện một loại không ổn định; tức là, nếu hai phần tử bằng nhau, thứ tự của chúng có thể không được giữ nguyên. Ngược lại, một loại ổn định bảo tồn thứ tự các phần tử bằng nhau.

Chức năng sắp xếp được sử dụng trong mẫu làm cho 1 == 3, 1 == 5 để sắp xếp không ổn định được phép đặt số này theo bất kỳ cách nào miễn là đúng thứ tự: 1,3,5 (ổn định - cùng thứ tự như trong nguồn) hoặc bất kỳ chuỗi nào 3,1,5 (sắp xếp không ổn định).

I.e. OrderBy thực hiện "loại ổn định" và bạn có thể xem kết quả trong sau mẫu sử dụng cùng chức năng so sánh:

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

Answer 3

Đó là mã tương đương với:

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

tôi nhận được:

{3, 5, 1, 2, 4} 

Thao tác sắp xếp như sau:

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} 

Vì vậy, trong kết luận, có vẻ như "tại sao" là bởi vì 0 vấn đề như mọi người nói, nhưng tôi chưa hoàn thành chắc chắn chưa.

Answer 4

đây là làm thế nào tôi hiểu nó, căn cứ vào mã, bạn có thể thay đổi nó như:

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

nên arrary.sort, được sắp xếp với điều kiện (OnComparison, mà theo giá trị trả về), không so sánh với số int []. vì vậy 3 1, cả hai trở lại dưới dạng -1 và như định nghĩa của mảng.sắp xếp:

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

rằng tại sao, bạn có {3, 5, 1, 2, 4}

Answer 5

Ở đây bạn không dư loại bằng cách bạn có để

thử điều này:

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