1.排序算法
1.1冒泡排序
1.1.1算法描述（摘自网络）
原始算法：
1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
3. 针对所有的元素重复以上的步骤，除了最后一个；
4. 重复步骤1~3，直到排序完成。
算法优化：
每一轮步骤1~3排序结束后，如果没有进行排序操作，则表示整个数组已经满足了升序或者降序的顺序，不需要继续排序了，此时退出循环排序，节省时间。
1.1.2算法实现
输入：
Src：一个数组
Order：0是降序，1是升序
Opt：默认为True，使用优化算法，False为原始排序算法
@time_count
def bubble(src: list, order=1, opt=True):
# src: list
# order: 0 descend, 1 ascend
# opt: True optimize, False not optimize
# print(src)
dst = src.copy()
step = 0
for i in range(len(dst)-1, 0, -1):
sorted = not opt
for j in range(i):
step += 1
if (order and dst[j] > dst[j+1]) or (not order and dst[j] < dst[j+1]):
temp = dst[j]
dst[j] = dst[j+1]
dst[j+1] = temp
sorted = True
if not sorted:
print('no need to sort')
break
print('step', step)
return dst
1.2选择排序
1.2.1算法描述（摘自网络）
原始算法：
1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
2. 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3. 重复第二步，直到所有元素均排序完毕。
算法优化：
1. 步骤1同时找出最大和最小值，找出的最大和最小值分别存放在各自的序列中，排序完成后输出两个序列的组合。
2. 如果最大值和最小值是同一个值，说明剩下的所有数据都是相同的，可直接退出排序。
1.2.2算法实现
原始算法：
@time_count
def select_origin(src: list, order=1):
# src: list
# order: 0 descend, 1 ascend
# print(src)
dst_temp = src.copy()
dst = []
while len(dst_temp):
max_id = 0
for i in range(1, len(dst_temp)):
if dst_temp[i] > dst_temp[max_id]:
max_id = i
if order == 0:
dst.append(dst_temp[max_id])
else:
dst.insert(0, dst_temp[max_id])
dst_temp.pop(max_id)
return dst
优化算法：
@time_count
def select_opt(src: list, order=1):
# src: list
# order: 0 descend, 1 ascend
# print(src)
dst_temp = src.copy()
dst_min = []
dst_max = []
while len(dst_temp):
max_id = 0
min_id = 0
for i in range(1, len(dst_temp)):
if dst_temp[i] > dst_temp[max_id]:
max_id = i
if dst_temp[i] < dst_temp[min_id]:
min_id = i
if max_id == min_id:
if order == 0:
dst_max += dst_temp
else:
dst_max = dst_temp + dst_max
break
if order == 0:
dst_max.append(dst_temp[max_id])
dst_min.insert(0,dst_temp[min_id])
else:
dst_max.insert(0, dst_temp[max_id])
dst_min.append(dst_temp[min_id])
if max_id > min_id:
dst_temp.pop(max_id)
dst_temp.pop(min_id)
elif max_id < min_id:
dst_temp.pop(min_id)
dst_temp.pop(max_id)
else:
dst_temp.pop(min_id)
if order == 0:
return dst_max + dst_min
else:
return dst_min + dst_max
1.3插入排序
1.3.1算法描述（摘自网络）
原始算法：
1. 把待排序的数组分成已排序和未排序两部分，初始的时候把第一个元素认为是已排好序的。
2. 从第二个元素开始，在已排好序的子数组中寻找到该元素合适的位置并插入该位置。
3. 重复上述过程直到最后一个元素被插入有序子数组中。
算法优化1：
在步骤2中，计算待插入的值靠近序列的开头还是末尾，靠近哪一侧，就从该侧寻找位置插入，减少循环查找的次数。
算法优化2：
在步骤2中，计算待插入的值靠近序列的开头、中间还是末尾，，靠近哪一侧，就从该侧寻找位置插入，进一步减少循环查找的次数。
1.3.2算法实现
原始算法：
@time_count
def insert_origin(src: list, order=1):
# src: list
# order: 0 descend, 1 ascend
# print(src)
dst = src[0:1]
for i in range(1, len(src)):
inserted = False
for j in range(len(dst)):
if (order and src[i] < dst[j]) or (not order and src[i] > dst[j]):
dst.insert(j, src[i])
inserted = True
break
if not inserted:
dst.append(src[i])
return dst
优化算法1：
@time_count
def insert_opt1(src: list, order=1):
# src: list
# order: 0 descend, 1 ascend
# print(src)
dst = src[0:1]
for i in range(1, len(src)):
inserted = False
if abs(src[i]-dst[0]) <= abs(src[i]-dst[-1]):
for j in range(len(dst)):
if (order and src[i] < dst[j]) or (not order and src[i] > dst[j]):
dst.insert(j, src[i])
inserted = True
break
if not inserted:
dst.append(src[i])
else:
for j in range(len(dst)-1,-1,-1):
if (order and src[i] > dst[j]) or (not order and src[i] < dst[j]):
dst.insert(j+1, src[i])
inserted = True
break
if not inserted:
dst.insert(0,src[i])
return dst
优化算法2：
@time_count
def insert_opt2(src: list, order=1):
# src: list
# order: 0 descend, 1 ascend
# print(src)
dst = src[0:1]
def insert_left(src_vlaue, from_mid=False):
inserted = False
start = 0 if not from_mid else int(len(dst)/2)
for j in range(start, len(dst)):
if (order and src_vlaue < dst[j]) or (not order and src_vlaue > dst[j]):
dst.insert(j, src_vlaue)
inserted = True
break
if not inserted:
dst.append(src_vlaue)
def insert_right(src_vlaue, from_mid=False):
inserted = False
start = len(dst)-1 if not from_mid else int(len(dst)/2)
for j in range(start,-1,-1):
if (order and src_vlaue > dst[j]) or (not order and src_vlaue < dst[j]):
dst.insert(j+1, src_vlaue)
inserted = True
break
if not inserted:
dst.insert(0, src_vlaue)
for i in range(1, len(src)):
l = abs(src[i]-dst[0])
r = abs(src[i]-dst[-1])
m = src[i]-dst[int(len(dst)/2)]
if l <= abs(m) and l <= r:
insert_left(src[i])
elif r <= abs(m) and r <= l:
insert_right(src[i])
else:
if m >= 0:
insert_left(src[i], True)
else:
insert_right(src[i], True)
return dst
2.算法比较
2.1算法有效性
为证明算法能有效进行排序，使用的数组为：
data0 = [0, 7, 7, -2, 1, -7, 7, 7, 6, -2, 0, 10, 9, 9, 4, 2, 6, 5, 1, 8, 3, 1, 10, 7, -1]
分别使用各个算法进行升序和降序。
1）冒泡排序：
>>> bubble(data0)
no need to sort
step 297
cost 1
[-7, -2, -2, -1, 0, 0, 1, 1, 1, 2, 3, 4, 5, 6, 6, 7, 7, 7, 7, 7, 8, 9, 9, 10, 10]
>>> bubble(data0, 0)
no need to sort
step 297
cost 1
[10, 10, 9, 9, 8, 7, 7, 7, 7, 7, 6, 6, 5, 4, 3, 2, 1, 1, 1, 0, 0, -1, -2, -2, -7]
>>> bubble(data0,opt=False)
step 300
cost 2
[-7, -2, -2, -1, 0, 0, 1, 1, 1, 2, 3, 4, 5, 6, 6, 7, 7, 7, 7, 7, 8, 9, 9, 10, 10]
>>> bubble(data0, 0, opt=False)
step 300
cost 2
[10, 10, 9, 9, 8, 7, 7, 7, 7, 7, 6, 6, 5, 4, 3, 2, 1, 1, 1, 0, 0, -1, -2, -2, -7]
2）选择排序
>>> select_opt(data0)
cost 0
[-7, -2, -2, -1, 0, 0, 1, 1, 1, 2, 3, 4, 5, 6, 6, 7, 7, 7, 7, 7, 8, 9, 9, 10, 10]
>>> select_opt(data0,0)
cost 0
[10, 10, 9, 9, 8, 7, 7, 7, 7, 7, 6, 6, 5, 4, 3, 2, 1, 1, 1, 0, 0, -1, -2, -2, -7]
>>> select_origin(data0)
cost 0
[-7, -2, -2, -1, 0, 0, 1, 1, 1, 2, 3, 4, 5, 6, 6, 7, 7, 7, 7, 7, 8, 9, 9, 10, 10]
>>> select_origin(data0,0)
cost 0
[10, 10, 9, 9, 8, 7, 7, 7, 7, 7, 6, 6, 5, 4, 3, 2, 1, 1, 1, 0, 0, -1, -2, -2, -7]
>>>
3）插入排序
>>> insert_opt1(data0)
cost 0
[-7, -2, -2, -1, 0, 0, 1, 1, 1, 2, 3, 4, 5, 6, 6, 7, 7, 7, 7, 7, 8, 9, 9, 10, 10]
>>> insert_opt1(data0, 0)
cost 0
[10, 10, 9, 9, 8, 7, 7, 7, 7, 7, 6, 6, 5, 4, 3, 2, 1, 1, 1, 0, 0, -1, -2, -2, -7]
>>> insert_origin(data0)
cost 0
[-7, -2, -2, -1, 0, 0, 1, 1, 1, 2, 3, 4, 5, 6, 6, 7, 7, 7, 7, 7, 8, 9, 9, 10, 10]
>>> insert_origin(data0, 0)
cost 0
[10, 10, 9, 9, 8, 7, 7, 7, 7, 7, 6, 6, 5, 4, 3, 2, 1, 1, 1, 0, 0, -1, -2, -2, -7]
>>> insert_opt2(data0)
cost 0
[-7, -2, -2, -1, 0, 0, 1, 1, 1, 2, 3, 4, 5, 6, 6, 7, 7, 7, 7, 7, 8, 9, 9, 10, 10]
>>> insert_opt2(data0, 0)
cost 0
[10, 10, 9, 9, 8, 7, 7, 7, 7, 6, 6, 7, 5, 1, 3, 1, 2, 4, 1, 0, 0, -1, -2, -2, -7]
>>>
2.2算法比较
使用三组数据比较各个算法的计算时长。
数组1长度为1万，其数值为0~100的随机数。
数组2长度为10万，其数值为0~100的随机数。
数组3长度为1万，其数值前5000为0~100的随机数，后5000为升序的值。
import random
import datetime
data1 = [random.randint(-100,100) for i in range(10000)]
data2 = [random.randint(-100,100) for i in range(100000)]
data3 = [random.randint(-100,100) for i in range(5000)] + [i for i in range(5000)]
使用datetime计算算法执行的时长。
def time_count(func):
def wrapper(*args, **kwargs):
start = datetime.datetime.now()
result = func(*args, **kwargs)
print('cost', int((datetime.datetime.now() - start).total_seconds()*1000))
return result
return wrapper
每个算法，对同一组数据，计算5次升序，取平均值，单位是ms，结果如下：
算法 |
冒泡排序 |
选择排序 |
插入排序 |
|||||||||
原始 |
优化 |
提升 |
原始 |
优化 |
提升 |
原始 |
优化1 |
优化2 |
提升1 |
提升2 |
||
数据1（1w） |
降序 |
11998 |
11976 |
0.19% |
3498 |
3146 |
10.08% |
2323 |
1178 |
281 |
49.28% |
87.89% |
升序 |
11760 |
11765 |
-0.05% |
3517 |
3143 |
10.63% |
2278 |
1169 |
527 |
48.66% |
76.84% |
|
数据2（10w） |
降序 |
1263493 |
1263487 |
0.00% |
351886 |
316437 |
10.07% |
230149 |
119339 |
28089 |
48.15% |
87.80% |
升序 |
1251652 |
1251670 |
0.00% |
354900 |
315789 |
11.02% |
234406 |
118856 |
53412 |
49.29% |
77.21% |
|
数据3（1w） |
降序 |
15113 |
15112 |
0.01% |
3671 |
3209 |
12.58% |
593 |
324 |
91 |
45.38% |
84.65% |
升序 |
8693 |
6665 |
23.32% |
3688 |
3203 |
13.14% |
3917 |
308 |
145 |
92.15% |
96.30% |
|
备注：提升=(原始-优化)/原始*100%
图1 数据1降序排序各算法耗时
图2 数据1升序排序各算法耗时
结论：
1、原始算法排序效率：插入排序>选择排序>冒泡排序。
2、冒泡排序，对于乱序的数据1和数据2，优化算法与原始算法用时接近，无优化效果，对特殊顺序的数组3，升序的优化算法有明显的提升，降序也无优化效果。
3、选择排序和插入排序的优化算法对各组数据均能生效。
4、选择排序的优化算法对各组数据的均提升约10%。
5、插入排序的优化效果相比于其他两个算法的优化效果提升最大。
6、插入排序的效率：优化算法2>优化算法1>原始算法。
说明：以上实验并未严格控制测试环境，数据仅供参考。
