基于python的冒泡排序和选择排序
0.产生7000长度的乱序列表
import random
a_list = list(range(1,7000 + 1))
normal_list = random.sample(a_list, k=len(a_list))
normal_list[:5]上面一段代码的运行结果如下，因为是随机打乱顺序，读者运行结果会不同：
[2780, 397, 5063, 6494, 1245]
0.1 保存此乱序列表
import pickle
with open('normal_list.pickle', 'wb') as file:
pickle.dump(normal_list, file)0.2 加载此乱序列表
import pickle
with open('normal_list.pickle', 'rb') as file:
normal_list = pickle.load(file)0.3 计时装饰器
装饰器是python的高级用法，初学者需要单独学习1天才能理解并且熟练运用。 读者如果不理解本节内容，不影响后续内容的理解。 此装饰器只是计算函数运行花费的时间，读者可以自己用其他方法实现相同效果。
from time import time
def timer(func):
def inner(*args,**kwargs):
start = time()
result = func(*args,**kwargs)
end = time()
usedTime = 1000 * (end - start)
print("%s function used %.2f ms" %(func.__name__,usedTime))
return result
return inner1.冒泡排序
@timer
def bubble_sort(normal_list):
length = len(normal_list)
for i in range(length, 1, -1):
for j in range(0, i-1):
if normal_list[j] > normal_list[j+1]:
normal_list[j], normal_list[j+1] = normal_list[j+1], normal_list[j]
with open('normal_list.pickle', 'rb') as file:
normal_list = pickle.load(file)
bubble_sort(normal_list)
print(normal_list[:10])
print(normal_list[-10:])上面一段代码的运行结果如下：
bubble_sort function used 7858.98 ms [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] [6991, 6992, 6993, 6994, 6995, 6996, 6997, 6998, 6999, 7000]
2.选择排序
@timer
def select_sort(normal_list):
length = len(normal_list)
new_list = []
for i in range(length, 1, -1):
max_index = 0
max_value = normal_list[0]
for j in range(1, i):
if normal_list[j] > max_value:
max_value = normal_list[j]
max_index = j
normal_list[i-1], normal_list[max_index] = normal_list[max_index], normal_list[i-1]
with open('normal_list.pickle', 'rb') as file:
normal_list = pickle.load(file)
select_sort(normal_list)
print(normal_list[:10])
print(normal_list[-10:])上面一段代码的运行结果如下：
select_sort function used 2018.90 ms [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] [6991, 6992, 6993, 6994, 6995, 6996, 6997, 6998, 6999, 7000]
3.结论
虽然冒泡排序和选择排序的时间复杂度都是O(n^2)，但是经过实践检验，在python实现2种排序算法后，选择排序花费的时间明显第冒泡排序花费的时间。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.11.08 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录