def insertion_sort(L):
for i in range(1,len(L)):
x = i
while x > 0 and L[x-1] >= L[x]:
x -= 1
value = L[i]
del L[i]
L.insert(x,value)
a = [5,2,6,3,1,8]
print "Before: ", a
insertion_sort(a)
print "After: ", a
По какой-то причине список не отсортирован должным образом. Я не могу найти ошибку здесь.Алгоритм сортировки вставки не работает
В четвертой строке должно быть:
while x > 0 and L[x-1] >= L[i]:
Вместо
while x > 0 and L[x-1] >= L[x]:
@alfasin Будет полезно, если вы можете дать мне случай, когда он не будет работать. –
Плохо, (смиренно исправлено!) – alfasin
От Wikipedia:
for i ← 1 to length(A) - 1
j ← i
while j > 0 and A[j-1] > A[j]
swap A[j] and A[j-1]
j ← j - 1
end while
end for
Чтобы перевести на Python:
def insertion_sort(A):
for i in range(1, len(A)):
j = i
while j > 0 and A[j-1] > A[j]:
swap(A, j, j-1)
j = j - 1
def swap(A, f, t):
A[t], A[f] = A[f], A[t]
a = [5,2,6,3,1,8]
print "Before: ", a
insertion_sort(a)
print "After: ", a
Попробуйте это ..
def insertion_sort(L):
for i in range(1, len(L)):
val = L[i]
x = i - 1
while (x >= 0) and (L[x] > val):
L[x + 1] = L[x]
x = x - 1
L[x + 1] = val
a = [5, 2, 6, 3, 1, 8]
print "Before: ", a
insertion_sort(a)
print "After: ", a
Обратите внимание, что если вы не делаете это чисто для практики цели, вы, вероятно, следует использовать модуль Bisect: https://docs.python.org/2.7/library/ bisect.html – vermillon