Позвольте мне попытаться сломать это.
Начните с рассмотрения списка.Это "почти" отсортировано.То есть первые несколько элементов отсортированы, но последний элемент не отсортирован.Так что это выглядит примерно так:
[10, 20, 30, 50, 15]
Очевидно, 15 находится не в том месте.Так как мы это передвинем?
key = mylist[4]
mylist[4] = mylist[3]
mylist[3] = key
Это переключится вокруг 15 и 50, поэтому теперь список выглядит так:
[10, 20, 30, 15, 50]
Но мы бы хотели сделать это несколько раз в цикле.Чтобы сделать это, мы можем сделать:
while ???:
key = mylist[i]
mylist[i] = mylist[i-1]
mylist[i-1] = key
i -= 1
Этот цикл будет возвращаться на одну позицию за раз, меняя местами два элемента.Это будет перемещать позицию не по порядку на одно место каждый раз.Но как мы узнаем, когда остановиться?
Давайте еще раз посмотрим на наш список и ходы, которые мы хотим сделать:
[10, 20, 30, 50, 15]
[10, 20, 30, 15, 50]
[10, 20, 15, 30, 50]
[10, 15, 20, 30, 50]
# stop! we are sorted now!
Но что отличается от этого в прошлый раз?Каждый раз, когда мы перемещаем место номер один назад, это происходит потому, что 15 меньше, чем элемент слева, что означает, что он не отсортирован.Когда это уже не так, мы должны перестать двигаться.Но мы можем легко справиться с этим:
key = mylist[i]
while key < mylist[i-1]:
mylist[i] = mylist[i-1]
mylist[i-1] = key
i -= 1
Хорошо, но произойдет, если мы сейчас попытаемся отсортировать этот список:
[10, 20, 1] [10, 1, 20][1, 10, 20] # ОШИБКА !!
В этот момент происходит что-то плохое.Мы пытаемся проверить, является ли ключ
Если мы достигнем начала списка, мы не сможем продвинуть нашу пивот / клавишу дальше, поэтому мы должны остановиться.Мы обновляем наш цикл while для обработки этого:
key = mylist[i]
while i > 0 and key < mylist[i-1]:
mylist[i] = mylist[i-1]
mylist[i-1] = key
i -= 1
Так что теперь у нас есть метод сортировки почти отсортированного списка.Но как мы можем использовать это для сортировки всего списка?Мы сортируем части списка за раз.
[8, 2, 4, 9, 3, 6]
Сначала мы сортируем первые 1 элементы:
[8, 2, 4, 9, 3, 6]
Затем мы сортируем первые 2 элемента:
[2, 8, 4, 9, 3, 6]
Затем мы сортируем первые 3 элемента
[2, 4, 8, 9, 3, 6]
И так далее и тому подобное
[2, 4, 8, 9, 3, 6]
[2, 4, 8, 9, 3, 6]
[2, 3, 4, 8, 9, 6]
[2, 3, 4, 6, 8, 9]
Но как нам это сделать?С циклом for
for j in range(len(mylist)):
i = j
key = mylist[i]
while i > 0 and key < mylist[i-1]:
mylist[i] = mylist[i-1]
mylist[i-1] = key
i -= 1
Но мы можем пропустить первый раз, потому что список одного элемента, очевидно, уже отсортирован.
for j in range(1, len(mylist)):
i = j
key = mylist[i]
while i > 0 and key < mylist[i-1]:
mylist[i] = mylist[i-1]
mylist[i-1] = key
i -= 1
Несколько незначительных изменений, которые не имеют значениявозвращает нас к исходному коду
for j in range(1, len(mylist)):
key = mylist[j]
i = j
while i > 0 and key < mylist[i-1]:
mylist[i] = mylist[i-1]
i -= 1
mylist[i] = key