转载请注明出处：

排序>>选择排序>>选择排序

List:

0.概念+示例分析

1.插入排序实现

0 start

基本概念：

维基百科

插入排序，简单来说就是每次拿一个新的数，将其插入到有序序列中.

示例：

[8, 4, 3, 1, 6, 9, 2, 7]

index- 1  #从第二个数开始

move 1 , change-> [

4, 8

, 3, 1, 6, 9, 2, 7]  #移动一次，插入

index- 2

move 2 , change-> [

3

, 4, 8

, 1, 6, 9, 2, 7] #移动两次，插入

index- 3

move 3 , change-> [

1

, 3, 4, 8

, 6, 9, 2, 7]

index- 4

move 1 , change-> [

1, 3, 4,

6

, 8

, 9, 2, 7]

index- 5

move 0 ,  nochange -> [1, 3, 4, 6, 8, 9, 2, 7]

index- 6

move 5 , change-> [

1,2, 3, 4, 6, 8, 9

, 7]

index- 7

move 2 , change-> [

1, 2, 3, 4, 6,

7

, 8, 9

]

[1, 2, 3, 4, 6, 7, 8, 9]

1 start

插入排序python实现

#!/usr/bin/python# -*- coding:utf-8 -*-#插入排序#@author: wklken@yeah.netdef insert_sort(l):    print l    for i in range(1,len(l)): #从第二个元素开始        value = l[i]        while i >= 1 and l[i-1] > value:            l[i] = l[i-1]            i -= 1        l[i] = value    return l    l = [8, 4, 3, 1, 6, 9, 2, 7]print insert_sort(l)

改进及优化：

1.加入监控，已排序完成直接退出

2.使用二分插入排序，即，处理某个节点往前插入的时候，使用二分查找插入