Home  >  Article  >  Backend Development  >  Detailed explanation of simple analysis and code examples of using the insertion sort algorithm in Python

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

高洛峰
高洛峰Original
2017-03-06 13:32:561283browse

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!

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn