插入排序(英语:Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
执行以上代码输出结果为:
排序后的数组: 5 6 11 12 13
小花花
124***[email protected]
主函数迭代次数:数值个数n 0.5n(n + 1)。
"""插入排序
InsertionSort.py"""
# 一次往数组添加多个数字
def AppendNumbers(array):
num = input('Numbers:(split by spaces)\t').split()
for i in num:
array.append(int(i))
print('排序前数组:{}.'.format(array))
def InsertionSort(array):
AppendNumbers(array) # 添加
list = []
while True:
for i in array:
minimum = min(array)
if i == minimum:
list.append(i)
array.remove(i) # 删去最小值
if array == []:
break
print('排序后数组:{}.'.format(list))
array = [6, 4, 45, -2, -1, 2, 4, 0, 1, 2, 3, 4, 5, 6, -4, -6, 7, 8, 8, 34, 0]
InsertionSort(array)小花花
124***[email protected]
陈某某
904***[email protected]
参考方法:
arr = [1,12,2, 11, 13, 5, 6,18,4,9,-5,3,11] def insertionSort(arr): #从要排序的列表第二个元素开始比较 for i in range(1,len(arr)): j = i #从大到小比较,直到比较到第一个元素 while j > 0: if arr[j] < arr[j-1]: arr[j-1],arr[j] = arr[j],arr[j-1] j -= 1 return arr print(insertionSort(arr))
陈某某
904***[email protected]
大嘴
144***[email protected]
参考:
def insertionSort(): import random random.seed(888) data=[] for i in range(15): data.append(random.randint(1, 100)) print(data) for i in range(1,len(data)): temp=data[i] for j in reversed(range(i)): if temp<data[j]: data[j+1],data[j]=data[j],temp print(data) insertionSort()
大嘴
144***[email protected]
我是一只菜菜鸟
348***[email protected]
另外的实现方法:
# 插入排序算法实现 def insertionSort(list): n = len(list) for i in range(1,n): #默认数列中的第一个元素已排好,故从第二个元素开始插入 j = i while list[j] < list[j-1] and j>0: #和已经排好序的数从右往左比较,小于则交换位置 list[j],list[j-1] = list[j-1],list[j] j-=1 return list list=[2,1,0,5,7,4,0] print(insertionSort(list))
我是一只菜菜鸟
348***[email protected]
sky
127***[email protected]
关键在于两组数据,一个是排好的 b,一个是待处理的 a。待处理的(第二个 for)如果小于处理好的,就插入,然后删除原来的。没有替换的关系
l=[2,5,1,4,6,9,3,0,8,7] for a in range(1,len(l)): for b in range(0,a): if l[a]<l[b]: l.insert(b,l[a]) del l[a+1] print(l)
输出结果为:
[1, 2, 5, 4, 6, 9, 3, 0, 8, 7] [1, 2, 4, 5, 6, 9, 3, 0, 8, 7] [1, 2, 3, 4, 5, 6, 9, 0, 8, 7] [0, 1, 2, 3, 4, 5, 6, 9, 8, 7] [0, 1, 2, 3, 4, 5, 6, 8, 9, 7] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
sky
127***[email protected]