Câu hỏi Tại sao Collections.sort sử dụng sắp xếp hợp nhất thay vì quicksort? [đã đóng]


Chúng ta biết rằng sắp xếp nhanh là thuật toán sắp xếp nhanh nhất.

Collections.sort đã sử dụng thuật toán sắp xếp hợp nhất thay vì sắp xếp nhanh. Nhưng Arrays.sort sử dụng sắp xếp nhanh chóng.

Lý do Collections.sort sử dụng sắp xếp hợp nhất thay vì sắp xếp nhanh là gì?


76
2018-03-01 09:12


gốc


Trừ khi bạn có thể nhận được một tác giả JDK để trả lời, tất cả các bạn sẽ nhận được là phỏng đoán. Không phải là một câu hỏi thực sự. - user207421
@EJP Điểm tốt, nhưng chắc chắn "Không xây dựng" là lý do đóng cửa đúng. Rõ ràng với tôi câu hỏi ở đây là gì. - Duncan Jones
Bởi vì các chàng trai Java đã quyết định làm như thế này. Hỏi họ. Bạn không thể có được một câu trả lời hợp pháp ở đây tôi nghĩ. Và sắp xếp nhanh là không phải tốt nhất. Nó chỉ là tốt nhất cho sử dụng chung. - Adam Arold
Một đoán: Quicksort không ổn định, Mergesort là. Đối với nguyên thủy, một loại ổn định / không ổn định là không liên quan, đối với các đối tượng có thể là (hoặc ít nhất, bạn có thể nhận được các lỗi được gửi chống lại một loại không ổn định). - parsifal
@EJP, Không có gì ngăn cản các ý định của các tác giả JDK được công khai. Khi nó được công khai, chúng ta không cần chính tác giả trả lời. Trên thực tế, có thể nhận được câu trả lời thậm chí còn hơn cả đoán ngay cả khi không có trả lời của tác giả JDK. - Pacerier


Các câu trả lời:


Rất có thể từ Josh Bloch §:

Tôi đã viết những phương pháp này, vì vậy tôi cho rằng tôi đủ điều kiện để trả lời. Nó là   đúng là không có thuật toán phân loại tốt nhất. QuickSort có   hai thiếu sót lớn khi so sánh với mergesort:

  1. Nó không ổn định (như phân tích cú pháp).

  2. Nó không Bảo hành n log n hiệu suất; nó có thể làm suy giảm hiệu suất bậc hai trên đầu vào bệnh lý.

Tính ổn định không phải là vấn đề đối với các loại nguyên thủy, vì không có khái niệm về   danh tính khác biệt với (giá trị) bình đẳng. Và khả năng   hành vi bậc hai được coi là không phải là một vấn đề trong thực tế   Triển khai mạnh mẽ và McIlroy (hoặc sau đó cho Dual Pivot   Sắp xếp nhanh chóng), đó là lý do tại sao các biến thể QuickSort này được sử dụng cho   các loại nguyên thủy.

Tính ổn định là một vấn đề lớn khi phân loại các đối tượng tùy ý. Ví dụ,   giả sử bạn có các đối tượng đại diện cho thông điệp email và bạn sắp xếp   chúng đầu tiên theo ngày, sau đó bởi người gửi. Bạn mong đợi chúng được sắp xếp theo   ngày trong mỗi người gửi, nhưng điều đó sẽ chỉ đúng nếu sắp xếp là   ổn định. Đó là lý do tại sao chúng tôi đã chọn để cung cấp một loại ổn định (Merge Sort)   để sắp xếp các tham chiếu đối tượng. (Techincally nói, nhiều tuần tự   các loại ổn định dẫn đến thứ tự từ điển trên các phím trong   thứ tự đảo ngược của các loại: loại cuối cùng xác định nhiều nhất   khoá con quan trọng.)

Đó là một lợi ích phụ tốt đẹp mà Merge sắp xếp đảm bảo n log n (thời gian)   hiệu suất bất kể đầu vào là gì. Tất nhiên có một mặt xuống:   sắp xếp nhanh chóng là một loại "tại chỗ": nó chỉ đáp ứng log n không gian bên ngoài   (để duy trì ngăn xếp cuộc gọi). Hợp nhất, sắp xếp, mặt khác,   yêu cầu không gian bên ngoài O (n). Biến thể TimSort (được giới thiệu trong Java   SE 6) yêu cầu không gian ít hơn đáng kể (O (k)) nếu mảng đầu vào là   gần như sắp xếp.

Ngoài ra, tiếp theo là có liên quan:

Thuật toán được sử dụng bởi java.util.Arrays.sort và (gián tiếp) bởi   java.util.Collections.sort để sắp xếp các tham chiếu đối tượng là một "sửa đổi   mergesort (trong đó hợp nhất bị bỏ qua nếu phần tử cao nhất trong   danh sách con thấp ít hơn yếu tố thấp nhất trong danh sách con cao). "   là một sắp xếp ổn định hợp lý đảm bảo O (n log n)   hiệu suất và yêu cầu thêm không gian (n). Trong ngày của nó (nó đã được viết   vào năm 1997 bởi Joshua Bloch), đó là một lựa chọn tốt, nhưng hôm nay nhưng chúng ta có thể   làm tốt hơn nhiều.

Từ năm 2003, sắp xếp danh sách của Python đã sử dụng thuật toán được gọi là timsort   (sau khi Tim Peters, người đã viết nó). Nó ổn định, thích nghi, lặp đi lặp lại   mergesort yêu cầu ít hơn so với n log (n) so sánh khi   chạy trên các mảng được sắp xếp một phần, trong khi cung cấp hiệu suất   so sánh với một mergesort truyền thống khi chạy trên các mảng ngẫu nhiên. Như   tất cả các định thời hợp nhất của timesort đều ổn định và chạy trong thời gian O (n log n)   (trường hợp xấu nhất). Trong trường hợp xấu nhất, timsort yêu cầu bộ nhớ tạm thời   không gian cho các tham chiếu đối tượng n / 2; trong trường hợp tốt nhất, nó chỉ đòi hỏi một   lượng không gian nhỏ liên tục. Tương phản điều này với dòng điện   triển khai, luôn yêu cầu thêm không gian cho đối tượng n   tài liệu tham khảo, và đánh bại n log n chỉ trên danh sách gần như sắp xếp.

Timsort được mô tả chi tiết tại đây:    http://svn.python.org/projects/python/trunk/Objects/listsort.txt.

Triển khai ban đầu của Tim Peters được viết bằng C. Joshua Bloch   chuyển nó từ C sang Java và kết thúc thử nghiệm, đo điểm chuẩn và điều chỉnh   kết quả mã rộng rãi. Mã kết quả là một trình đơn thả xuống   thay thế cho java.util.Arrays.sort. Trên dữ liệu có thứ tự cao, điều này   mã có thể chạy nhanh gấp 25 lần so với hiện tại (trên   máy chủ HotSpot VM). Trên dữ liệu ngẫu nhiên, tốc độ cũ và mới   triển khai có thể so sánh được. Đối với danh sách rất ngắn, danh sách mới   thực hiện nhanh hơn đáng kể so với tuổi   dữ liệu (vì nó tránh sao chép dữ liệu không cần thiết).

Cũng thấy Java 7 có sử dụng Tim Sort cho phương thức Arrays.Sort không?.

Không có một lựa chọn "tốt nhất" nào. Như với nhiều thứ khác, đó là về sự cân bằng.


156
2018-03-01 09:20