Хан вдохновил сортировка вставками


Я просто смотрел в Академии Хана видео на сортировка вставкой и я пытался написать реализацию на Python. Пожалуйста, предложите исправления или улучшения по этой программе:

unsorted_list=[45,99,1,-22,7,3,294,10,36]

def insertion_sort(unsorted):
    for i in range(1,len(unsorted)):
        for j in range(i):
            if unsorted[i]<unsorted[j]:
                temp = unsorted[j]    
                unsorted[j]=unsorted[i]
                unsorted[i]=temp

    return unsorted 

print insertion_sort(unsorted_list)


Комментарии
3 ответа

Я бы не стал называть свою реализацию сортировки вставками, как это сортировка с помощью свопов, которые, как отметил Дэвид делает его более похожим на пузырьковой сортировки. В сортировка вставками сортировка посредством строительства нового списка и вставка элементов в правильном месте. Очень сырой первый проход на сортировка вставками может выглядеть так:

def insertion_sort(unsorted_list):
result = []
for n in unsorted_list:
inserted = False
for i in range(len(result)):
if n < result[i]:
result.insert(i, n)
inserted = True
break
if not inserted:
result.append(n)
return result

Это может быть значительно улучшена для больших наборов данных, сделав внутренний поиск воспользоваться тем, что с сортировки и бинарного поиска для курсора. Конечно, это питон, весь этот бардак можно было бы оптимизировать, чтобы отсортированный(unsorted_list). ;)

6
ответ дан 5 июля 2011 в 09:07 Источник Поделиться

И замены в Python могут быть выполнены менее трудоемкий способ:

unsorted[i], unsorted[j] = unsorted[j], unsorted[i]

5
ответ дан 3 июля 2011 в 02:07 Источник Поделиться

Название несортированный список, который в конечном итоге будет отсортирована страшно.

Назвать это the_list или что-то еще. Но не дать ему имя, которое -- в конце insertion_sort функция будет неправдой. Дать ему имя, которое всегда будет истинным.

2
ответ дан 11 июля 2011 в 04:07 Источник Поделиться