73
Какой алгоритм построен в методе sort() в Python с использованием? Можно ли взглянуть на код этого метода?О встроенном методе sort() метода Python
A
ответ
84
Конечно! Код here, начиная с функции islt и заканчивая QUITE a; ;-). Как замечает Крис, это код C. Вы также захотите прочитать текстовый файл this для текстового объяснения, результатов и т. Д.
Если вы предпочитаете читать Java-код, чем код C, вы можете посмотреть реализацию Joshua Bloch timsort в Java и для Java (Joshua's также парень, который в 1997 году внедрил модифицированный mergesort, который все еще используется в Java, и можно надеяться, что Java в конечном итоге переключится на его последний порт timsort).
Некоторые объяснения порта Java из timsort является here, то дифф here (с указателями на все необходимые файлы), ключевой файл является here - FWIW, в то время как я лучше C программист, чем Java программист, в в этом случае я нахожу код Java Joshua более читабельным в целом, чем код C Тима ;-).
+3
+1 для того, чтобы знать, где это было. –
+4
@Chris, «Просмотр источников Python» - это ярлык во всех барах закладок моих браузеров - он указывает на http://svn.python.org/view/python/trunk/ ;-). –
+0
Я хочу знать, что делает функция 'list_ass_item()'. :) –
7
В ранних версиях python функция sort реализовала модифицированную версию quicksort. Однако он считался нестабильным, и по состоянию на 2.3 они переключились на использование адаптивного алгоритма слияния.
23
Я просто хотел предоставить очень полезную ссылку, которую я пропустил в полном ответе Алекса: A high-level explanation of Python's timsort (с визуализацией графа!).
(Да, алгоритм в основном известен как Timsort сейчас)
+0
Ссылка кажется сломанной. – kzorro
+0
Я установил ссылку. – twasbrillig
Конечно, можно посмотреть на код метода - Python является проектом с открытым исходным кодом. Однако метод, вероятно, реализован на C, поэтому вам нужно немного узнать о C, чтобы понять его. –
Имеет ли значение версия? –
@melder: No =) Я просто хочу взглянуть на про-алгоритм: P @chris: как? – Johannes