用户工具

站点工具


algorithm:insert-sort

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 numbers:') #输入逗号分隔整数列 如:7,6,5,1,8,34
for item in input.split(','):
    A.append(int(item))
 
InsertionSort(A)#插入排序
print A

参考

algorithm/insert-sort.txt · 最后更改: 2010/06/02 01:18 (外部编辑)