Thuật toán nào làm trình biên dịch C++ phổ biến sử dụng cho std :: sort và std :: stable_sort? Tôi biết tiêu chuẩn chỉ cung cấp các yêu cầu hiệu suất nhất định, nhưng tôi muốn biết các thuật toán phổ biến nào được sử dụng trong thực tế.Thuật toán nào làm trình biên dịch C++ phổ biến sử dụng cho std :: sort và std :: stable_sort?
Câu trả lời sẽ hữu ích hơn nếu nó trích dẫn các tham chiếu cho từng triển khai.
Trước hết: trình biên dịch không cung cấp bất kỳ triển khai std::sort nào. Trong khi theo truyền thống, mỗi trình biên dịch được đóng gói sẵn với việc thực hiện Thư viện chuẩn (phụ thuộc rất nhiều vào các trình biên dịch của trình biên dịch), bạn có thể trao đổi một lý thuyết cho một thực thi khác. Một ví dụ rất hay là Clang biên dịch cả libstdC++ (theo kiểu truyền thống với gcc) và libC++ (thương hiệu mới).
Bây giờ đây là ra khỏi con đường ...
std::sort có truyền thống được thực hiện như một intro-loại. Từ một quan điểm cấp cao, nó có nghĩa là thực hiện phân loại nhanh tương đối chuẩn (với một số thăm dò trung bình để tránh trường hợp xấu nhất O (n) cùng với một thói quen sắp xếp chèn cho đầu vào nhỏ. Tuy nhiên, việc triển khai libC++ hơi khác và gần với TimSort: nó phát hiện các chuỗi đã sắp xếp trong các đầu vào và tránh phân loại chúng một lần nữa, dẫn đến một hành vi O (n) trên đầu vào được sắp xếp đầy đủ. Nó cũng sử dụng các mạng phân loại tối ưu cho đầu vào nhỏ.
std::stable_sort mặt khác phức tạp hơn. Điều này có thể ngoại suy từ chính từ ngữ của Chuẩn: độ phức tạp là O (n log n) nếu đủ bộ nhớ bổ sung có thể được phân bổ (gợi ý: hợp nhất-loại), nhưng thoái hóa thành O (n log n) nếu không.
Tôi đã cố gắng để tìm "O (n lg^2 n)' "mergesort" trong một thời bây giờ. Nó chắc chắn không phải là một sự hợp nhất thông thường vì nó không sử dụng bộ nhớ thừa - nó có thể là gì? – VF1
@ VF1 Điều đó có lẽ sẽ hợp nhất sắp xếp với bước kết hợp O (n log n) tại chỗ. –
@NiklasB. Vâng, tôi đã nhận được nhiều, tôi đang tìm kiếm một bài viết sâu hơn. – VF1
Nếu chúng tôi lấy gcc làm ví dụ, chúng tôi thấy rằng đó là phần giới thiệu cho std::sort và hợp nhất cho std::stable_sort.
Nếu bạn lội qua libc++ code, bạn sẽ thấy rằng nó cũng sử dụng phối hợp cho std::stable_sort nếu phạm vi đủ lớn.
Một điều bạn cũng nên lưu ý là trong khi cách tiếp cận chung luôn là một trong những phương pháp được đề cập ở trên, chúng đều được tối ưu hóa cao cho các trường hợp đặc biệt khác nhau.
Introsort là sự kết hợp giữa phân loại nhanh, heapsort và chèn. – inf
@ phant0m: "trùng lặp" của bạn không đề cập đến stable_sort. –
Hmm đúng, tôi có thể đã được một chút kích hoạt hạnh phúc. Lấy làm tiếc. – phant0m