73
Thuật toán nào được xây dựng trong phương thức sort() trong Python bằng cách sử dụng? Có thể xem mã cho phương thức đó không?Giới thiệu về phương thức sắp xếp được xây dựng trong Python()
A
Trả lời
84
Chắc chắn! Mã số here, bắt đầu với hàm islt và tiếp tục QUITE một thời gian ;-). Như bình luận của Chris cho thấy, đó là mã C. Bạn cũng sẽ muốn đọc this tệp văn bản để giải thích văn bản, kết quả, v.v.
Nếu bạn thích đọc mã Java hơn mã C, bạn có thể xem Joshua Bloch thực hiện timsort trong và cho Java (Joshua's) người đã thực hiện, vào năm 1997, sáp nhập đã sửa đổi vẫn được sử dụng trong Java, và người ta có thể hy vọng rằng Java cuối cùng sẽ chuyển sang cổng thời gian gần đây của mình).
Một số giải thích về cổng Java của timsort là here, độ cách biệt here (với các con trỏ tới tất cả các file cần thiết), các tập tin quan trọng là here - FWIW, trong khi tôi là một lập trình viên C tốt hơn so với lập trình viên Java, trong trường hợp này tôi tìm thấy mã Java của Joshua dễ đọc hơn tổng thể so với mã C ,-) của Tim.
+3
+1 để biết vị trí nó đã được. –
+4
@Chris, "Duyệt nguồn Python" là lối tắt trong tất cả các thanh dấu trang của trình duyệt của tôi - nó trỏ tới http://svn.python.org/view/python/trunk/ ;-). –
+0
Tôi muốn biết hàm 'list_ass_item()' hoạt động như thế nào. :) –
7
Trong các phiên bản python đầu tiên, chức năng sắp xếp đã triển khai phiên bản sửa đổi của quicksort. Tuy nhiên, nó được coi là không ổn định và đến 2,3 họ chuyển sang sử dụng thuật toán hợp nhất thích ứng.
23
Tôi chỉ muốn cung cấp một liên kết rất hữu ích mà tôi đã bỏ lỡ trong câu trả lời khác của Alex: A high-level explanation of Python's timsort (với đồ thị trực quan!).
(Vâng, các thuật toán được về cơ bản được gọi là Timsort bây giờ)
+0
Liên kết dường như bị hỏng. – kzorro
+0
Tôi đã sửa liên kết. – twasbrillig
Tất nhiên nó có thể nhìn vào mã cho phương pháp này - Python là một dự án mã nguồn mở. Phương pháp này có thể được thực hiện trong C, tuy nhiên, vì vậy bạn sẽ phải biết một chút về C để làm cho bất kỳ ý nghĩa của nó. –
Phiên bản có quan trọng không? –
@melder: Không =) Tôi chỉ muốn xem thuật toán chuyên nghiệp: P @chris: làm cách nào? – Johannes