вставка сортировки не упорядочивает массив правильно
Вот моя сортировка вставки, точно так же, как в книге «Введение в алгоритмы»:
def insertion_sort(): A = [5,2,4,6,1,3] for j in range(1, len(A)): print 'j:'+str(j) key = A[j] print 'key:'+str(key) i=j-1 print 'i:'+str(i) while i > 0 and A[i] > key: A[i+1] = A[i] i=i-1 print 'new i: '+str(i) print 'swapping value: '+str(A[i]) + ' with value: '+str(A[i+1]) print ' ' A[i+1] = key print A Это печатает:
[5, 1, 2, 3, 4, 6]
Что я делаю неправильно, чтобы они были не в порядке?
Во Введении к Алгоритмам они всегда предполагают, что массивы начинаются с индекса 1, поэтому вы начинаете свой range() в 1 , но списки python индексируются на основе 0. Это означает, что вы никогда не сравниваете 5 , то есть A[0] . Заметьте все после сортировки 5 .
изменение вашего цикла for –
for j in range(0, len(A)):
и ваше состояние
while i >= 0 and A[i] > key:
Должен сделать трюк.