# 实现原理
将数组分为两部分，左边为有序集合，右边为无序集合，
取右边集合的第一个元素与左边的集合挨个对比，直到插入合适的位置。
# 原理图
暂无
# 实现一：平移法
inputArr = [10, 34, 29, 4, 0, 34, 5, 4, 36, 1, 8]
length = len(inputArr)
print("未排序集合:{0}".format(inputArr))
# 从第1个元素开始作为无须集合
for rightIndex in range(1, length):
rightItem = inputArr[rightIndex]
# 待插入位置
insertIndex = rightIndex
# 查找待插入位置
while(insertIndex != 0):
if(rightItem > inputArr[insertIndex-1]):
break
insertIndex -= 1
if(rightIndex == insertIndex):
continue
# 向后平移元素
while (insertIndex != rightIndex):
inputArr[rightIndex] = inputArr[rightIndex-1]
rightIndex -= 1
# 插入正确的位置
inputArr[insertIndex] = rightItem
print("已排序集合:{0}".format(inputArr))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 实现二：交换法
inputArr = [10, 34, 29, 4, 0, 34, 5, 4, 36, 1, 8]
length = len(inputArr)
print("未排序集合:{0}".format(inputArr))
# 从第1个元素开始作为无须集合
for rightIndex in range(1, length):
# 从有序集合由右到左依次比较知道插入正确的位置
while(rightIndex != 0):
if(inputArr[rightIndex] > inputArr[rightIndex-1]):
break
inputArr[rightIndex], inputArr[rightIndex-1]\
= inputArr[rightIndex-1], inputArr[rightIndex]
rightIndex -= 1
print("已排序集合:{0}".format(inputArr))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 区别
平移法： 当找到待插入位置后，之后的元素无脑后移一位，然后插入元素
交换法： 不关心插入位置，总是从有序集合的第一位比较到最后一位然后结束
