О встроенном в Python методе sort ()

104

Какой алгоритм использует встроенный sort()метод в Python? Можно ли посмотреть код этого метода?

Йоханнес
источник
11
Конечно, можно посмотреть код метода - Python - проект с открытым исходным кодом. Однако этот метод, вероятно, реализован на C, поэтому вам нужно немного узнать о C, чтобы понять его.
Крис Лутц,
Версия имеет значение?
медер омуралиев 04
@melder: Нет =) Я просто хочу взглянуть на профессиональный алгоритм: P @chris: как?
Йоханнес,
3
Загрузите исходный код в интерпретатор Python. Я не знаю, где они реализуют sort()метод или каково форматирование интерпретатора, но он должен быть где-то там, и я уверен, что он реализован на C из соображений скорости.
Крис Лутц,
Вот пример его использования
Хари Ганесан

Ответы:

119

Конечно! Код здесь , начинается с функции isltи продолжается некоторое время ;-). Как следует из комментария Криса, это код C. Вы также захотите прочитать этот текстовый файл для текстового объяснения, результатов и т. Д.

Если вы предпочитаете читать Java-код, а не C-код, вы можете взглянуть на реализацию Timsort Джошуа Блоха в Java и для Java (Джошуа также разработал в 1997 году модифицированную сортировку слиянием, которая все еще используется в Java, и можно надеяться, что Java будет со временем переключаюсь на свой недавний порт тимсорт).

Некоторое объяснение Java-порта timsort здесь , diff здесь (с указателями на все необходимые файлы), ключевой файл здесь - FWIW, хотя я лучше программист на C, чем Java-программист, в этом случае я нахожу Java-код Джошуа в целом более читабелен, чем код Тима на C ;-).

Алекс Мартелли
источник
4
@Chris, «Обзор источников Python» - это ярлык на всех панелях закладок моих браузеров - он указывает на svn.python.org/view/python/trunk ;-).
Алекс Мартелли,
Я хочу знать, что list_ass_item()делает эта функция . :)
Крис Лутц
2
Выполняет присвоение элементу списка (точно так же, как list_ass_slice выполняет присвоение части списка), не имеет ничего общего с сортировкой. Я думаю, аббревиатура от "assignment" делает название забавным ...
Alex Martelli
3
Текущая версия из listsort.txtдобавляет некоторые примечания , что адрес общего замешательства.
Тим Питерс
9

В ранних версиях python функция сортировки реализовывала модифицированную версию быстрой сортировки. Однако это было сочтено нестабильным, и с 2.3 они перешли на использование алгоритма адаптивной сортировки слиянием.

Silfverstrom
источник
быстрая сортировка не считается «нестабильной» - согласно обычно используемым определениям, быстрая сортировка нестабильна - то есть исходный порядок двух объектов не сохраняется, если они равны во время этой сортировки. Наличие нестабильного алгоритма сортировки означает, что вам нужно придумывать всевозможные `` волшебства '' для разумной сортировки данных по нескольким критериям, а не просто иметь возможность связывать вызовы сортировки - в timsort, если вы хотите отсортировать по DOB, а затем назвать , вы просто сортируете сначала по имени, а затем по дате рождения. Вы не можете этого сделать с помощью быстрой сортировки
Тони Саффолк 66