几个排序算法的效率比较
2020-03-19 本文已影响0人
thepoy
排序算法文件
# -*- coding: utf-8 -*-
# sorts.py
from utils import clocking
@clocking
def p_sort(m: list, r: list):
l = m.copy()
print('自带排序：')
l.sort()
return l == r
@clocking
def quick_sort(m: list, r: list):
"""
找到一个基准值，将列表数字与其比较大小后分为两组，两组通过相同的方法再次比较大小，周而复始直到分组后的列表只有1个或0个元素结束
:param m:
:return:
"""
print('快速排序：')
l = m.copy()
def _sort(l: list):
if len(l) < 2:
return l
else:
base = l[0] # 找一个基准值比较大小，基准值随便找
less = [i for i in l[1:] if i < base]
greater = [i for i in l[1:] if i >= base]
return _sort(less) + [base] + _sort(greater)
return _sort(l) == r
@clocking
def bubble_sort(m: list, r: list) -> bool:
"""
把较大的数字向后移动
:param m:
:return:
"""
l = m.copy()
print('冒泡排序：')
for i, v1 in enumerate(l):
for j, v2 in enumerate(l[i:-1]):
if l[j] > l[j + 1]:
l[j], l[j + 1] = l[j + 1], l[j]
return l == r
@clocking
def select_sort1(m: list, r: list):
"""
找到除当前元素外的最小值后，与当前元素交换位置
:param m:
:return:
"""
print('快速排序1：')
l = m.copy()
for i, v1 in enumerate(l):
min_index = i
for j, v2 in enumerate(l[i + 1:]):
if v2 < l[min_index]:
min_index = j + i + 1 # enumerate方法return的索引是从0开始的，需要转换为原列表索引
l[i], l[min_index] = l[min_index], l[i]
return l == r
@clocking
def select_sort2(m: list, r: list):
"""
假设当前值为最小值，如果后面有比它小的就交换二者的位置
:param m:
:param r:
:return:
"""
print('快速排序2：')
l = m.copy()
for i, v1 in enumerate(l):
for j, v2 in enumerate(l[i + 1:]):
if l[i] > l[j + i + 1]:
l[i], l[j + i + 1] = l[j + i + 1], l[i]
return l == r
@clocking
def insert_sort(m: list, r: list):
"""
把小的数据插入到第一个比它大的数前面
:param m:
:param r:
:return:
"""
print('插入排序：')
l = m.copy()
for i, v1 in enumerate(l):
for j, v2 in enumerate(l[:i]):
if v2 > v1:
l.insert(j, v1)
l.pop(i + 1)
break # 插入到第一个比i大的值前后，就退出
return l == r
if __name__ == '__main__':
l = [9690, 9117, 9855, 4910, 6208, 505, 3362, 5764, 2223, 8202, 476, 8771, 9969, 2466, 4918, 587, 9253, 582, 2782, 1294, 1737, 1144, 9998, 7814, 7968, 6359, 3867, 7949, 4058, 4518, 4737, 5445, 4380, 5156, 305, 5104, 7424, 2659, 6223, 4748, 9911, 2807, 4059, 3372, 1539, 4386, 924, 8408, 7808, 7140, 9618, 6835, 4565, 4451, 2968, 9829, 3817, 278, 4245, 2170, 382, 1633, 8032, 2888, 3914, 6210, 2700, 1474, 1701, 1757, 4554, 8992, 9755, 7757, 2941, 7802, 3123, 1708, 7400, 8613, 5783, 5285, 1388, 2858, 8652, 6826, 1213, 4290, 5147, 8666, 878, 4806, 5525, 9295, 6341, 5740, 1514, 3738, 9840, 4879]
r = [278, 305, 382, 476, 505, 582, 587, 878, 924, 1144, 1213, 1294, 1388, 1474, 1514, 1539, 1633, 1701, 1708, 1737, 1757, 2170, 2223, 2466, 2659, 2700, 2782, 2807, 2858, 2888, 2941, 2968, 3123, 3362, 3372, 3738, 3817, 3867, 3914, 4058, 4059, 4245, 4290, 4380, 4386, 4451, 4518, 4554, 4565, 4737, 4748, 4806, 4879, 4910, 4918, 5104, 5147, 5156, 5285, 5445, 5525, 5740, 5764, 5783, 6208, 6210, 6223, 6341, 6359, 6826, 6835, 7140, 7400, 7424, 7757, 7802, 7808, 7814, 7949, 7968, 8032, 8202, 8408, 8613, 8652, 8666, 8771, 8992, 9117, 9253, 9295, 9618, 9690, 9755, 9829, 9840, 9855, 9911, 9969, 9998]
p_sort(l, r)
quick_sort(l, r)
bubble_sort(l, r)
select_sort1(l, r)
select_sort2(l, r)
insert_sort(l, r)
计时器(clocking)文件：
# -*- coding: utf-8 -*-
# utils.py
import time
def clocking(fn):
def wrapper(*args, **kwargs):
start = time.time() * 10 ** 6
result = fn(*args, **kwargs)
end = time.time() * 10 ** 6
runtime = end - start
print(f'结果：{result}\n耗时：{runtime} 微秒\n{"*"*40}')
return wrapper
结果：
自带排序：
结果：True
耗时：65.0 微秒
****************************************
快速排序：
结果：True
耗时：463.75 微秒
****************************************
冒泡排序：
结果：True
耗时：2145.5 微秒
****************************************
快速排序1：
结果：True
耗时：1436.75 微秒
****************************************
快速排序2：
结果：True
耗时：3726.25 微秒
****************************************
插入排序：
结果：True
耗时：913.25 微秒
****************************************
以上结果是对稍大的无序整数列表进行排序，如果列表元素少，结果会不一样
