Tại sao Danh sách <T>. Sắp xếp lại phương thức sắp xếp bằng IComparable <T> yếu tố?

Question

Tôi gặp sự cố với cách phương thức sắp xếp danh sách xử lý sắp xếp. Với các yếu tố sau:

class Element : IComparable<Element> 
{ 
    public int Priority { get; set; } 
    public string Description { get; set; } 

    public int CompareTo(Element other) 
    { 
     return Priority.CompareTo(other.Priority); 
    } 
} 

Nếu tôi cố gắng sắp xếp nó theo cách này:

List<Element> elements = new List<Element>() 
          { 
           new Element() 
            { 
             Priority = 1, 
             Description = "First" 
            }, 
           new Element() 
            { 
             Priority = 1, 
             Description = "Second" 
            }, 
           new Element() 
            { 
             Priority = 2, 
             Description = "Third" 
            } 
          }; 
elements.Sort(); 

Sau đó, các yếu tố đầu tiên là yếu tố trước đây thứ hai "Thứ hai". Hoặc nói cách khác, xác nhận này không thành công:

Assert.AreEqual("First", elements[0].Description); 

Tại sao .NET sắp xếp lại danh sách của tôi khi các yếu tố cơ bản giống nhau? Tôi muốn cho nó để chỉ sắp xếp lại danh sách nếu so sánh trả về một giá trị khác không.

Answer 1

Từ các tài liệu của phương pháp List.Sort() từ MSDN:

Phương pháp này sử dụng Array.Sort, trong đó sử dụng các thuật toán Sắp xếp nhanh. Việc triển khai 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.

Đây là liên kết: http://msdn.microsoft.com/en-us/library/b0zbh7b6.aspx

Về cơ bản, loại được thực hiện như thiết kế và tài liệu.

Answer 2

Bạn đã nói với nó cách so sánh mọi thứ và nó đã làm. Bạn không nên dựa vào việc triển khai nội bộ của Sắp xếp trong ứng dụng của bạn. Đó là lý do tại sao nó cho phép bạn ghi đè CompareTo. Nếu bạn muốn có tham số sắp xếp thứ cấp ("mô tả" trong trường hợp này), hãy mã hóa nó vào CompareTo của bạn. Dựa vào cách sắp xếp chỉ xảy ra với công việc là một cách tuyệt vời để viết mã trong một lỗi rất khó tìm.

Bạn có thể tìm thấy một quicksort ổn định cho .NET hoặc sử dụng merge sort (đã ổn định).

Answer 3

Bạn có thể sửa lỗi này bằng cách thêm "giá trị chỉ mục" vào cấu trúc của mình và bao gồm trong phương thức CompareTo khi Priority.CompareTo trả về 0. Sau đó, bạn cần phải khởi tạo giá trị "chỉ mục" trước khi thực hiện sắp xếp.

Các CompareTo phương pháp sẽ trông như thế này:

public int CompareTo(Element other) 
{ 
    var ret = Priority.CompareTo(other.Priority); 
    if (ret == 0) 
    { 
     ret = Comparer<int>.Default.Compare(Index, other.Index); 
    } 
    return ret; 
} 

Sau đó, thay vì làm elements.Sort(), bạn sẽ làm gì:

for(int i = 0; i < elements.Count; ++i) 
{ 
    elements[i].Index = i; 
} 
elements.Sort(); 

Answer 4

Xem các câu trả lời khác cho lý do tại sao List.Sort() là không ổn định. Nếu bạn cần một loại ổn định và đang sử dụng .NET 3.5, hãy thử Enumerable.OrderBy() (LINQ).

Answer 5

Nếu bạn muốn sắp xếp dựa trên hai lĩnh vực thay vì một trong những bạn có thể làm điều này:

class Element : IComparable<Element> 
{ 
    public int Priority { get; set; } 
    public string Description { get; set; } 

    public int CompareTo(Element other) 
    { 
     if (Priority.CompareTo(other.Priority) == 0) 
     { 
      return Description.CompareTo(other.Description); 
     } else { 
      return Priority.CompareTo(other.Priority); 
     } 
    } 
} 

Rõ ràng, điều này không đáp ứng các yêu cầu của một thuật toán tìm kiếm ổn định; Tuy nhiên, nó thỏa mãn sự khẳng định của bạn và cho phép kiểm soát thứ tự phần tử của bạn trong trường hợp bình đẳng.

Answer 6

Dưới đây là một phương pháp khuyến nông SortStable() cho List<T> where T : IComparable<T>:

public static void SortStable<T>(this List<T> list) where T : IComparable<T> 
{ 
    var listStableOrdered = list.OrderBy(x => x, new ComparableComparer<T>()).ToList(); 
    list.Clear(); 
    list.AddRange(listStableOrdered); 
} 

private class ComparableComparer<T> : IComparer<T> where T : IComparable<T> 
{ 
    public int Compare(T x, T y) 
    { 
     return x.CompareTo(y); 
    } 
} 

Test:

[Test] 
public void SortStable() 
{ 
    var list = new List<SortItem> 
        { 
         new SortItem{ SortOrder = 1, Name = "Name1"}, 
         new SortItem{ SortOrder = 2, Name = "Name2"}, 
         new SortItem{ SortOrder = 2, Name = "Name3"}, 
        }; 

    list.SortStable(); 

    Assert.That(list.ElementAt(0).SortOrder, Is.EqualTo(1)); 
    Assert.That(list.ElementAt(0).Name, Is.EqualTo("Name1")); 
    Assert.That(list.ElementAt(1).SortOrder, Is.EqualTo(2)); 
    Assert.That(list.ElementAt(1).Name, Is.EqualTo("Name2")); 
    Assert.That(list.ElementAt(2).SortOrder, Is.EqualTo(2)); 
    Assert.That(list.ElementAt(2).Name, Is.EqualTo("Name3")); 
} 

private class SortItem : IComparable<SortItem> 
{ 
    public int SortOrder { get; set; } 
    public string Name { get; set; } 

    public int CompareTo(SortItem other) 
    { 
     return SortOrder.CompareTo(other.SortOrder); 
    } 
} 

Trong phương pháp kiểm tra, nếu bạn gọi Sắp xếp() phương pháp thay vì SortStable(), bạn có thể thấy rằng thử nghiệm sẽ thất bại.

Answer 7

Trong một số ứng dụng, khi danh sách các mục được sắp xếp theo một số tiêu chí, việc bảo quản thứ tự ban đầu của các mục so sánh bằng không cần thiết. Trong các ứng dụng khác, nó là cần thiết. Các phương thức sắp xếp để bảo toàn sắp xếp các mục có khóa khớp (thường được gọi là "loại ổn định" thường chậm hơn nhiều so với các loại không ("loại không ổn định"), hoặc nếu chúng yêu cầu dung lượng lưu trữ tạm thời (và vẫn còn chậm hơn một chút) "Thư viện chuẩn" sắp xếp thường lệ để trở nên phổ biến có lẽ là hàm qsort() có trong thư viện C chuẩn. Thư viện đó thường xuyên được sử dụng để sắp xếp các danh sách lớn tương đối so với tổng số bộ nhớ có sẵn. đã ít hữu ích hơn nhiều nếu nó yêu cầu một lượng lưu trữ tạm thời tỷ lệ thuận với số lượng các mục trong mảng cần sắp xếp. lưu trữ tạm thời nhiều hơn sẽ có thể chấp nhận được trong C qsor t() thường trình. Một yêu cầu bộ nhớ tạm thời bằng với kích thước của mảng sẽ được sắp xếp trong hầu hết các trường hợp không gây ra bất kỳ vấn đề cụ thể nào. Tuy nhiên, vì nó đã được truyền thống cho các thư viện để cung cấp một triển khai Quicksort, mà có vẻ là mô hình tiếp theo.