Trong phương thức Danh sách <T> .Sort(), là một mục có được so sánh với chính nó không?

Question

Nếu tôi chuyển vào một IComparer tùy chỉnh cho một thể hiện của phương thức Sort() của Danh sách, phương thức Compare (x, y) của trình so sánh có được gọi với cùng một mục không?

tức là. Có thể là Compare(x,x) có thể được gọi.

Chỉnh sửa: Quan tâm hơn đến trường hợp các mục trong danh sách là riêng biệt.

Answer 1

Tôi đã viết một chương trình thử nghiệm để dùng thử. Có vẻ như nó thực sự là không So sánh() cùng một yếu tố với chính nó (ít nhất Compare() được gọi cho cùng một mục hai lần). Trong chương trình này, Compare() được gọi với các đối số (2, 2).

using System; 
using System.Collections.Generic; 

static class Program 
{ 
    class MyComparer : Comparer<int> 
    { 
     public override int Compare(int x, int y) 
     { 
      Console.WriteLine("Compare(" + x + ", " + y + ")"); 
      if (x < y) return -1; 
      if (x > y) return 1; 
      return 0; 
     } 
    } 

    static void Main() 
    { 
     MyComparer comparer = new MyComparer(); 
     List<int> list = new List<int> { 1, 2, 3 }; 
     list.Sort(comparer); 
     return; 

    } 
} 

Và kết quả là:

Compare(1, 2) 
Compare(1, 3) 
Compare(2, 3) 
Compare(1, 2) 
Compare(2, 2) 
Compare(2, 3) 
Compare(2, 2) 

Answer 2

Từ docs:

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.

QuickSort sẽ không bao giờ so sánh một mục với chính nó. Một số triển khai của QuickSort so sánh các mục với chính chúng. Điều này cũng có thể xảy ra nếu mục đó xảy ra nhiều lần trong Danh sách của bạn.

Dù bằng cách nào, để chức năng so sánh của bạn trở thành một hàm so sánh đúng đắn, đúng đắn, bạn cần xử lý trường hợp các yếu tố được so sánh với chính chúng.

Answer 3

Mặc dù nó không được bảo đảm nghiêm ngặt, tôi chắc rằng phương thức sắp xếp của Danh sách sẽ không bao giờ gọi phương thức so sánh của bạn để so sánh một đối tượng với chính nó trừ khi đối tượng đó xuất hiện trong danh sách nhiều lần. Tôi căn cứ kết luận này trên thực tế là List.Sort được triển khai bằng thuật toán QuickSort (theo MSDN), mà không bao giờ so sánh thường không liên quan đến việc so sánh cùng một yếu tố với chính nó (và không làm bất kỳ việc phân loại tài liệu nào các thuật toán tôi có thể nghĩ đến). (Chỉnh sửa: Có vẻ như việc triển khai của Microsoft so sánh phần tử với chính nó. Hãy xem câu trả lời được chấp nhận ở trên.)

Tuy nhiên, thực hành mã hóa tốt sẽ chỉ ra việc triển khai IComparer của bạn có thể xử lý được truyền cùng một đối tượng trong cả hai tham số, nếu không, việc triển khai của bạn sẽ không hoàn thành hợp đồng do IComparer xác định. Nó có thể làm việc cho kịch bản của bạn, nhưng bạn sẽ dựa vào các chi tiết thực hiện của phương thức sắp xếp (có thể thay đổi trong tương lai), và bạn sẽ không thể sử dụng được IComparer trong các tình huống khác mà không có đảm bảo (hoặc tệ hơn, bạn hoặc người khác KHÔNG sử dụng nó và có thể gây khó khăn khi tìm lỗi).

Answer 4

câu trả lời khác, chương trình này dựa trên the XML part of ECMA-335, các đặc điểm kỹ thuật của BCL (Base Class Library). Mặc dù không được bảo đảm để liên quan đến những gì thực hiện thực hiện, điều này là có thẩm quyền như nó được. Và thông số kỹ thuật không nêu gì ngoài:

Tại điều tồi tệ nhất, thao tác này là O (n^2), trong đó n là số phần tử cần sắp xếp. Trung bình nó là O (n log n).

Mặc dù đây là gợi ý của QuickSort, điều này hoàn toàn không đảm bảo. Thông số kỹ thuật cũng không yêu cầu triển khai theo điều khoản của Array.Sort.

Điểm mấu chốt: theo như thông số kỹ thuật có liên quan, hoàn toàn ổn cho việc triển khai để so sánh các mục với chính chúng.