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
赞 (0)

相关推荐

  • python sort、sorted高级排序技巧

    Python list内置sort()方法用来排序,也可以用python内置的全局sorted()方法来对可迭代的序列排序生成新的序列. 1)排序基础 简单的升序排序是非常容易的.只需要调用sorted()方法.它返回一个新的list,新的list的元素基于小于运算符(__lt__)来排序. 复制代码 代码如下: >>> sorted([5, 2, 3, 1, 4]) [1, 2, 3, 4, 5] 你也可以使用list.sort()方法来排序,此时list本身将被修改.通常此方法不如s

  • 浅谈插入排序算法在Python程序中的实现及简单改进

    Python实现插入排序的一般范例为: #coding=cp936 #coding=cp936 #插入排序算法 def InsertionSort(A): for j in range(1,len(A)): key = A[j] i = j-1 #向前查找插入位置 while i>=0 and A[i]>key: A[i+1] = A[i] i = i-1 A[i+1] = key #初始化输入数据 A = [] input = raw_input('please input some num

  • python 快速排序代码

    复制代码 代码如下: def quick_sort(ls): return [] if ls == [] else quick_sort([y for y in ls[1:] if y < ls[0]]) + [ls[0]] + quick_sort([y for y in ls[1:] if y >= ls[0]]) if __name__ == '__main__': l1 = [3,56,8,1,34,56,89,234,56,231,45,90,33,66,88,11,22] l2 =

  • python里对list中的整数求平均并排序

    问题 定义一个int型的一维数组,包含40个元素,用来存储每个学员的成绩,循环产生40个0~100之间的随机整数, (1)将它们存储到一维数组中,然后统计成绩低于平均分的学员的人数,并输出出来. (2)将这40个成绩按照从高到低的顺序输出出来. 解决(python) #! /usr/bin python #coding:utf-8 from __future__ import division #实现精确的除法,例如4/3=1.333333 import random def make_scor

  • javascript与Python快速排序实例对比

    本文实例对比了javascript与Python快速排序实现方法.分享给大家供大家参考.具体如下: js实现方法: function quicksort(arr) { if (arr.length <= 1) return arr return quicksort(arr.filter(function (lt, i) {return i > 0 && lt < arr[0]})) .concat([arr[0]]) .concat(quicksort(arr.filte

  • Python实现字典依据value排序

    具体内容如下: 使用sorted将字典按照其value大小排序 >>> record = {'a':89, 'b':86, 'c':99, 'd':100} >>> sorted(record.items(), key=lambda x:x[1]) [('b', 86), ('a', 89), ('c', 99), ('d', 100)] sorted第一个参数要可迭代,可以为tuple, list >>> items = [(1, 'B'), (1,

  • Python实现堆排序的方法详解

    Python实现堆排序的方法详解

    本文实例讲述了Python实现堆排序的方法.分享给大家供大家参考,具体如下: 堆排序作是基本排序方法的一种,类似于合并排序而不像插入排序,它的运行时间为O(nlogn),像插入排序而不像合并排序,它是一种原地排序算法,除了输入数组以外只占用常数个元素空间. 堆(定义):(二叉)堆数据结构是一个数组对象,可以视为一棵完全二叉树.如果根结点的值大于(小于)其它所有结点,并且它的左右子树也满足这样的性质,那么这个堆就是大(小)根堆. 我们假设某个堆由数组A表示,A[1]为树的根,给定某个结点的下标i,

  • python字符串排序方法

    本文以实例形式简述了Python实现字符串排序的方法,是Python程序设计中一个非常实用的技巧.分享给大家供大家参考之用.具体方法如下: 一般情况下,python中对一个字符串排序相当麻烦: 一.python中的字符串类型是不允许直接改变元素的.必须先把要排序的字符串放在容器里,如list. 二.python中的list容器的sort()函数没返回值. 所以在python中对字符串排序往往需要好几行代码. 具体实现方法如下: >>> s = "string" >

  • python3.0 字典key排序

    IDLE 3.0 >>> dic = {"aa":1,"bb":2,"ab":3} >>> dic {'aa': 1, 'ab': 3, 'bb': 2} >>> for k in sorted(dic.keys()): print (k) aa ab ----------------------------------------------- 字典对象其实就是键-值对 下面是字典对象的添加

  • 用Python写冒泡排序代码

    python代码实现冒泡排序代码其实很简单,具体代码如下所示: 代码Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> 1 def bubbleSort(numbers): for j in xrange(len(numbers),-1,-1): for i in xrange(0,j-1,1): if numbers[i] > numbers[i+

  • Python实现快速排序和插入排序算法及自定义排序的示例

    一.快速排序 快速排序(Quicksort)是对冒泡排序的一种改进.由C. A. R. Hoare在1962年提出.它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 快速排序,递归实现 def quick_sort(num_list): """ 快速排序 """ if num_li

随机推荐