python 排序算法:插入排序
摘自:python 排序算法——插入排序
·
- 适用场景:一个新元素需要插入到一组已经是有序的数组中,或者是一组基本有序的数组排序。
- 比较性:排序时元素之间需要比较,所以为比较排序。
- 稳定性:从代码我们可以看出只有比较元素大于当前元素,比较元素才会往后移动,所以相同元素是不会改变相对顺序。
- 时间复杂度:插入排序同样需要两次循坏一个一个比较,故时间复杂度也为 O ( n 2 ) O(n^2) O(n2)。
- 空间复杂度:只需要常数个辅助单元,所以空间复杂度也为 O ( 1 ) O(1) O(1)。
案例
- 给定一个列表: [ 8 , 5 , 1 , 1 , 8 , 5 , 7 , 4 , 6 , 3 ] [8, 5, 1, 1, 8, 5, 7, 4, 6, 3] [8,5,1,1,8,5,7,4,6,3]
- 排序结果: [ 1 , 1 , 3 , 4 , 5 , 5 , 6 , 7 , 8 , 8 ] [1, 1, 3, 4, 5, 5, 6, 7, 8, 8] [1,1,3,4,5,5,6,7,8,8]
def insert_sort(tg_list):
''' 排序算法:插入排序 '''
for i in range(1,len(tg_list)):
for j in range(i,0,-1):
if tg_list[j] < tg_list[j-1]:
tg_list[j-1], tg_list[j] = tg_list[j], tg_list[j-1]
else:
break
list_ = [8, 5, 1, 1, 8, 5, 7, 4, 6, 3]
insert_sort(list_)
- 排序过程:
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...................................................... ......................................................
- 对超长序列计算排序耗时时间。
- 观察序列数量设置从100至10000,查看排序耗时走势。
- 代码
import pandas as pd
import random
import time
import seaborn as sns
import matplotlib.pyplot as plt
# 解决win 系统中文不显示问题
from pylab import mpl
mpl.rcParams['font.sans-serif']=['SimHei']
def insert_sort(tg_list):
''' 排序算法:插入排序 '''
for i in range(1,len(tg_list)):
for j in range(i,0,-1):
if tg_list[j] < tg_list[j-1]:
tg_list[j-1], tg_list[j] = tg_list[j], tg_list[j-1]
else:
break
def get_runtime(n):
''' 获取排序耗时 '''
time_start = time.clock() # 记录开始时间
list_ = [random.randint(1,n) for i in range(n)]
insert_sort(list_)
time_end = time.clock() # 记录结束时间
time_sum = time_end - time_start # 计算的时间差为程序的执行时间,单位为秒/s
return [n,time_sum]
def plot(df):
''' 绘制折线图 '''
pd.options.display.notebook_repr_html=False # 表格显示
plt.rcParams['figure.dpi'] = 75 # 图形分辨率
sns.set_style(style='darkgrid') # 图形主题
plt.figure(figsize=(4,3),dpi=150)
sns.lineplot(
data=df,
x='数量',
y='耗时(s)'
)
if __name__ == "__main__":
nums = range(100,10000,100)
res = list(map(get_runtime,nums))
res_df = pd.DataFrame(res,columns=['数量','耗时(s)'])
plot(res_df)
更多推荐
已为社区贡献8条内容
所有评论(0)