вставка сортировки не упорядочивает массив правильно

Вот моя сортировка вставки, точно так же, как в книге «Введение в алгоритмы»:

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: 

Должен сделать трюк.

Interesting Posts