Interview essential algorithm | graphic insertion sorting (Python)

Insertion sort

Insert the idea of sorting

​ Insert sort by building an ordered sequence , For unsorted data , Scan backward and forward in sorted series , Locate and insert . Insert sort in implementation , In the process of scanning from back to front , The elements have been moved back and forth , Provide insertion space for the latest elements .

Illustration insertion sort

 Insert picture description here

Nature of insert sort

  • Optimal time complexity : O ( n ) O(n) O(n) ( Ascending order , The sequence is already in ascending order )
  • Worst time complexity : O ( n 2 ) O(n^2) O(n2)
  • stability : Stable

Insert sort code implementation

lst = list(map(int, input().split(',')))
def insert_sort(alist):
n = len(alist)
for i in range(1, n):
j = i
for j in range(j, 0, -1):
if alist[j] < alist[j - 1]:
alist[j], alist[j - 1] = alist[j - 1], alist[j]
else:
break
return alist
insert_sort(lst)
Please bring the original link to reprint ,thank
Similar articles