Функция сортировки () python гарантированно стабильна?

The документация не гарантирует. Есть ли другое место, где это задокументировано?

Я предполагаю, что это может быть стабильным, так как метод сортировки в списках гарантированная стабильность (Примечания 9-й пункт:" начиная с Python 2.3, метод sort() гарантированно будет стабильным"), а сортировка функционально аналогична. Однако я не могу найти какой-либо определенный источник, который говорит об этом.

цель: мне нужно сортировать на основе первичных ключ и вторичный ключ в тех случаях, когда первичный ключ равен в обеих записей. Если sorted () гарантированно будет стабильным, я могу сортировать по вторичному ключу, а затем сортировать по первичному ключу и получать нужный мне результат.

PS: чтобы избежать путаницы, я использую stable в смысле "вид стабилен, если он гарантирует не изменять относительный порядок элементов, которые сравниваются равными".

5 68
python sortedset stable-sort

5 ответов:

да, намерение руководства состоит в том, чтобы гарантировать, что sorted стабильная и действительно, что он использует точно такой же алгоритм как sort метод. Я понимаю, что документы не на 100% ясны об этой идентичности; патчи doc всегда с радостью принимаются!

90

Они стабильный.

кстати: иногда вы можете игнорировать знание того, являются ли сортировка и сортировка стабильными, комбинируя многопроходную сортировку в однопроходной.

например, если вы хотите сортировать объекты на основе их last_name,first_name атрибуты, вы можете сделать это в один проход:

sorted_list= sorted(
    your_sequence_of_items,
    key= lambda item: (item.last_name, item.first_name))

используя преимущества сравнения кортежей.

этот ответ, как есть, охватывает исходный вопрос. Для дальнейшей сортировки вопросов, там есть Python Сортировка How-To.

23

документация изменилась в то же время (соответствующих совершения) и текущей документации sorted явно гарантирует это:

встроенный sorted() функция гарантированно будет стабильным. Сортировка является стабильной, если она гарантирует не изменять относительный порядок элементов, которые сравниваются равными - это полезно для сортировки в несколько проходов (например, сортировать по отделу, а затем по классу зарплаты).

этот часть документации была добавлена в Python 2.7 и Python 3.4 (+), так что все совместимость реализация этой языковой версии должна есть стабильной sorted.

обратите внимание, что для CPython list.sort был стабилен с Python 2.3

  • Тим Питерс переписал его list.sort() реализация-это "стабильная сортировка" (равные входы появляются в том же порядке на выходе) и быстрее, чем до.

Я не уверен на 100%sorted, в настоящее время он просто использует list.sort, но я не проверял историю для этого. Но вполне вероятно, что он" всегда " использовал list.sort.

2

The "Что нового" документы для Python 2.4 фактически сделайте так, чтобы sorted() сначала создавал список, а затем вызывал sort() на нем, предоставляя вам необходимую гарантию, хотя и не в "официальных" документах. Вы также можете просто проверить источник, если вы действительно обеспокоены.

0

Python 3.6 doc при сортировке теперь утверждает, что

сортировка гарантированно будет стабильной

кроме того, в этом документе есть ссылка на стабильный Timsort, где указано, что

Timsort был стандартным алгоритмом сортировки Python с версии 2.3

0