データ構造とアルゴリズムの実践-【並べ替えの挿入順序】並べ替えを挿入します。

転載は出典を明記してください。http://blog.csdn.net/wklken
ホームディレクトリ
並べ替え>>並べ替えの選択>>並べ替えの選択
リスト:
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
を2回移動させ、挿入
index-3
move 3，change->[
1
3,4,8
6,9,2,7]
index-4
move 1，change->[
1,3,4,
6
を選択します
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: [email protected]

def 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.二分挿入並べ替え、すなわち、あるノードを前に挿入する場合は、二分検索で挿入する