У меня есть две реализации сортировки вставки. Первая довольно много транскрипция, например, в моем учебнике Java (хотя и с while петли вместо Java for циклом)Что вызывает разницу в производительности между этими двумя реализациями сортировки вставки?
def insertion_sort(array):
for i in range(1,len(array)):
j = i
while j > 0 and array[j] < array[j-1]:
array[j],array[j-1] = array[j-1], array[j]
j=j-1
return array
вторых кажется более вещими реализации.
def insertion_sort2(array):
for i in range(1,len(array)):
for j in range(i-1,-1,-1):
if array[j+1] < array[j]:
array[j+1],array[j] = array[j],array[j+1]
else:
break
return array
После синхронизации обоих, кажется, второй намного медленнее (от 3 до 4 раз медленнее), когда список уже отсортирован, или почти отсортирован. Однако, по мере увеличения количества инверсий, вторая реализация, похоже, одерживает верх (на 10-15% быстрее). Мне просто интересно, может ли кто-нибудь объяснить, в чем причина этого несоответствия. Благодаря!
Редактировать: Вот функция, которую я использую для создания случайного списка.
def rand_list(length):
return [random.randint(0,9*length) for _ in range(length)]
Когда я хочу список, который частично отсортированных я просто называю list(range(length1)) + rand_list(length2).
Что касается сроков, сколько времени они берут для запуска, я использовал инструмент %timeit и разницу между двумя вызовами datetime.now(). Они дали довольно последовательные результаты. Также я хочу подчеркнуть, что каждый раз создаю новый список, не сортируя уже отсортированный список.
Это Python 2 или 3? если Python 2 попробует xrange, диапазон предварительно распределяет список в Python2, тогда как в Python3 он возвращает итератор. – totoro
Python 3, в частности 3.5.2. Я обновил теги, чтобы это отразить! – CopOnTheRun
@totoro Вопрос заключался не в том, как сделать это быстрее, а в том, чтобы * объяснить разницу * –