1.引例
打牌习惯性地将牌按照一定大小顺序排列,在摸牌过程中,每摸到一张牌,就会按照大小规则将它插入到手中的牌,这就是插入排序。
2.算法描述
插入排序分为两组数据,已经排序的数据。等待排序的数据,从等待排序的数据,向已经排序的数据中对比插入。
3.算法示图
4.代码实现
def InsertionSort(array):
# 从第二个元素开始遍历
for i in range(1,len(array)):
# 需要排序的元素
target = array[i]
# j表示已经排序好的数量
j = i-1
# 所有元素向后移动,直至target找到合适的位置
while(j>=0 and target<array[j]):
# 数据右移
array[j+1] = array[j]
j -= 1
# 如果j=0,说明target需要插入第一位。注意:此时while中判断为array[-1],在某些编译器中会出现数组值错误
# 避免错误的解决方式(在pythona中无需添加这段代码,fortran中需要添加,否则报错越界,需要注意的是在java中while判断中会出现array[-1]的情形,array[-1]不被准许,但由于j>=0已经为False,所以程序不再往后读取,直接退出循环,但某些编译器可能会出现问题)
if j==0:
break;
array[j+1] = target
print(array)
return array
if __name__ == '__main__':
arr = [344,4,345,78,5,68,9,4879,1548,44,23,99,14785,457,233]
InsertionSort(arr)
5.运行结果
[4, 344, 345, 78, 5, 68, 9, 4879, 1548, 44, 23, 99, 14785, 457, 233]
[4, 344, 345, 78, 5, 68, 9, 4879, 1548, 44, 23, 99, 14785, 457, 233]
[4, 78, 344, 345, 5, 68, 9, 4879, 1548, 44, 23, 99, 14785, 457, 233]
[4, 5, 78, 344, 345, 68, 9, 4879, 1548, 44, 23, 99, 14785, 457, 233]
[4, 5, 68, 78, 344, 345, 9, 4879, 1548, 44, 23, 99, 14785, 457, 233]
[4, 5, 9, 68, 78, 344, 345, 4879, 1548, 44, 23, 99, 14785, 457, 233]
[4, 5, 9, 68, 78, 344, 345, 4879, 1548, 44, 23, 99, 14785, 457, 233]
[4, 5, 9, 68, 78, 344, 345, 1548, 4879, 44, 23, 99, 14785, 457, 233]
[4, 5, 9, 44, 68, 78, 344, 345, 1548, 4879, 23, 99, 14785, 457, 233]
[4, 5, 9, 23, 44, 68, 78, 344, 345, 1548, 4879, 99, 14785, 457, 233]
[4, 5, 9, 23, 44, 68, 78, 99, 344, 345, 1548, 4879, 14785, 457, 233]
[4, 5, 9, 23, 44, 68, 78, 99, 344, 345, 1548, 4879, 14785, 457, 233]
[4, 5, 9, 23, 44, 68, 78, 99, 344, 345, 457, 1548, 4879, 14785, 233]
[4, 5, 9, 23, 44, 68, 78, 99, 233, 344, 345, 457, 1548, 4879, 14785]
6.来源——阳光沙滩微信公众号
链接:阳光沙滩插入排序算法