45fan.com - 路饭网

搜索: 您的位置主页 > 网络频道 > 阅读资讯:怎么样在Python中使用插入排序算法的分析代码?

怎么样在Python中使用插入排序算法的分析代码?

2016-06-15 06:40:57 来源:www.45fan.com 【

怎么样在Python中使用插入排序算法的分析代码?

问题描述

将一组随机排列的数字重新按照从小到大的顺序排列。

插入算法

每次从数组中取一个数字,与现有数字比较并插入适当位置。

如此重复,每次均可以保持现有数字按照顺序排列,直到数字取完,即排序成功。

这很像打牌时的抓牌情况,

第一个条件:保持手上的牌的顺序是正确的
第二个条件:每次抓到新的牌均按照顺序插入手上的牌中间。
保证这两条不变,那么无论抓了几张牌,最后手上的牌都是依照顺序排列的。

Python 实现:

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]]


另一个版本:

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

本文地址:http://www.45fan.com/a/question/53558.html
Tags: python 插入 排序
编辑:路饭网
关于我们 | 联系我们 | 友情链接 | 网站地图 | Sitemap | App | 返回顶部