Detailed explanation of simple analysis and code examples of using the insertion sort algorithm in Python

Problem description

Rearrange a set of randomly arranged numbers in order from small to large.

Insertion Algorithm

Take one number from the array at a time, compare it with the existing number and insert it into the appropriate position.

Repeat this way, each time you can keep the existing numbers in order until the numbers are taken out, that is, the sorting is successful.

This is very similar to the card drawing situation when playing cards.

The first condition: Keep the order of the cards in hand correct
The second condition: Each time you draw a new The cards are inserted into the middle of the cards in the hand in order.
Keep these two items unchanged, then no matter how many cards you draw, the cards in your hand will be arranged in order.

Python implementation:

def insertion_sort(n):
 if len(n) == 1:
  return n
 b = insertion_sort(n[1:])
 m = len(b)
 for i in range(m):
  if n[0] <= b[i]:
   return b[:i]+[n[0]]+b[i:]
 return b + [n[0]]

Another version:

def insertion_sort(lst):
 if len(lst) == 1:
  return lst

 for i in xrange(1, len(lst)):
  temp = lst[i]
  j = i - 1
  while j >= 0 and temp < lst[j]:
   lst[j + 1] = lst[j]
   j -= 1
  lst[j + 1] = temp
 return lst

For more detailed explanations of simple analysis and code examples of using the insertion sort algorithm in Python, please pay attention to the PHP Chinese website!