Python中使用插入排序算法的简单分析与代码示例

yipeiwu_com7年前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

相关文章

python TKinter获取文本框内容的方法

如下所示: #coding:utf-8 import urllib,urllib2 import Tkinter #导入TKinter模块 ytm=Tkinter.Tk() #创...

Python中Continue语句的用法的举例详解

Python中Continue语句的用法的举例详解

 Python continue语句返回while循环的开始。Continue语句拒绝在该循环的当前迭代中的其余语句执行并移动控制返回到循环的顶部(开始位置)。 continu...

pytorch在fintune时将sequential中的层输出方法,以vgg为例

有时候我们在fintune时发现pytorch把许多层都集合在一个sequential里,但是我们希望能把中间层的结果引出来做下一步操作,于是我自己琢磨了一个方法,以vgg为例,有点僵硬...

基于MATLAB和Python实现MFCC特征参数提取

基于MATLAB和Python实现MFCC特征参数提取

1、MFCC概述 在语音识别(Speech Recognition)和话者识别(Speaker Recognition)方面,最常用到的语音特征就是梅尔倒谱系数(Mel-scale Fr...

对python判断是否回文数的实例详解

对python判断是否回文数的实例详解

设n是一任意自然数。若将n的各位数字反向排列所得自然数n1与n相等,则称n为一回文数。例如,若n=1234321,则称n为一回文数;但若n=1234567,则n不是回文数。 上面的解释就...