一、插入排序
1.1 伪代码实现
插入排序(Insert sort)
for j <- 2 to n
do key <- A[j]
i <- j-1
while i > 0 and A[i] > key
do A[i+1] <- A[i]
i <- i-1
A[i+1] <- key
1.2 影响执行时间的因素
- 输入序列的次序
- 输入序列的大小
1.3 一些排序分析方法
- 最坏情况（常用）
T(n) = 最大执行时间 - 平均情况（有时）
T(n) = 期望执行时间 - 最好情况 （无用）
T(n) = 最小执行时间
1.4 渐近分析法(Asymptotic analysis)
- 忽略常数因子
- 仅仅关注增长速率(n -> 无穷大)
- O(n)定义为时间渐近复杂度
1.5 时间复杂度
T(n) = O(n^2)
二、合并排序
2.1 伪代码实现
合并排序(Merge sort)
1) if n = 1, done
2)Recursively sort A[1, ..., [n/2]] and A[[n/2]+1, ..., n]
3) Merge sorted lists
2.2 递归树
T(n) = 2T(n/2) + cn
2.3 时间复杂度
T(n) = cnlgn + O(n) = O(nlgn)
三、代码实现(python)
3.1 定义类初始化
import numpy as np
import time
import math
import matplotlib.pyplot as plt
class sort_list(object):
"面向对象编程，定义插入排序和合并排序的实现与分析方法"
def __init__(self, orig_list, n=20):
"""
初始化
:param orig_list:待排序的数组
"""
self.orig_list = orig_list
# 存储排序好的数组
self.sorted_list = None
# 执行时间
self.cost_time = None
# 画图时的点数
self.n = n
3.2插入排序实现
def insert_sort(self):
"对原序列进行插入排序"
# 计算序列元素量
num = len(self.orig_list)
# 赋值，对sorted_list进行操作
self.sorted_list = self.orig_list
# 从第二个元素开始遍历
for i in range(1, num):
tmp = self.sorted_list[i]
while i > 0 and self.sorted_list[i - 1] > tmp:
self.sorted_list[i] = self.sorted_list[i - 1]
i -= 1
self.sorted_list[i] = tmp
3.3合并排序实现
def merge_sort_function(self, orig_list):
"合并排序函数"
num = len(orig_list)
if num == 1:
return orig_list
# 递归
list1 = self.merge_sort_function(orig_list[:math.floor(num/2)])
list2 = self.merge_sort_function(orig_list[math.floor(num/2):])
# 两个有序序列的排序
new_list = []
while list1 and list2:
if list1[0] < list2[0]:
new_list.append(list1.pop(0))
else:
new_list.append(list2.pop(0))
if list1 or list2:
if list1:
return new_list + list1
else:
return new_list + list2
return new_list
def merge_sort(self):
"合并排序操作"
self.sorted_list = self.merge_sort_function(self.orig_list)
3.4 测试执行时间
def test_insert(self, print_cost=True):
"测试插入排序执行时间"
start = time.time()
self.insert_sort()
end = time.time()
self.cost_time = end - start
if print_cost:
print("Insert sort cost time :", self.cost_time)
def test_merge(self, print_cost=True):
"测试合并排序执行时间"
start = time.time()
self.merge_sort()
end = time.time()
self.cost_time = end - start
if print_cost:
print("Merge sort cost time :", self.cost_time)
3.5 记录n不同数量级的执行时间
def analysis_insert_and_merge(self):
"画图来直观的了解插入排序和合并排序的效率"
insert_times = []
merge_times = []
for i in range(self.n):
self.orig_list = list(np.random.random_integers(1, i*100 + 1, i*100 + 1))
self.test_insert(print_cost=False)
insert_times.append(self.cost_time)
self.test_merge(print_cost=False)
merge_times.append(self.cost_time)
plt.plot(insert_times, label="insert")
plt.plot(merge_times, label="merge")
plt.title("compare Insert sort and Merge sort")
plt.xlabel("n-1/100")
plt.ylabel("seconds")
plt.legend()
plt.show()
四、结果与分析
图
- 分析：n值在100 以内插入排序与合并排序的执行时间差别并不大，随着n值的不断增大，两种排序方法的效率的差异也随之增大。从上图可以看到当n为2000左右时，插入排序的时间损耗远远大于合并排序。
- 总结：在序列的数量级较小时，选用插入排序和合并排序差异并不大，可能选用插入排序效果会稍微好点；在序列的数量级较大时，选用合并排序的效率远远高于插入排序。
