Die Grundidee der Einfügungssortierung:
In jedem Schritt wird ein zu sortierender Datensatz entsprechend der Größe seines Schlüsselwerts an der entsprechenden Position der zuvor sortierten Datei eingefügt, bis alle vorhanden sind eingefügt.
Beispiel:
arr = [49,38,04,97,76,13,27,49,55,65], beginnend mit der zweiten Zahl als Schlüsselwert, vorwärts vergleichend Wenn die vorherige Zahl größer ist, tauschen Sie sie aus,
arr = [38,49,04,97,76,13,27,49,55,65] und verwenden Sie dann die dritte Zahl als Schlüssel Wert, vorwärts vergleichen, austauschen, wenn der erste größer ist,
arr = [38,04,49,97,76,13,27,49,55,65], und fortfahren, arr = [04 ,38, 49,97,76,13,27,49,55,65]
Hinweis: Beim Vergleich vorwärts in der Reihenfolge, da das vorherige Array geordnet ist, wenn die vorherige Zahl kleiner oder gleich ist Der Schlüsselwert. Diese Vorwärtsvergleichsschleife kann durchbrochen werden, und die Geschwindigkeit des Algorithmus wird erheblich verbessert.
Code:
def insert_sort(lists):
#插入排序
count = len(lists)
for i in range(1,count):#从第2个数起遍历
key = lists[i]
j = i - 1
while j >= 0:
if lists[j] > key:
lists[j+1], lists[j] = lists[j], key
else: break #当前一个数小于或等于key时，跳出循环
j -= 1
return lists
