|
def merge_sort(data, low, high):
"""
归并排序
:param data: 待排序的数据列表
:param low: 数据列表开始位置
:param high: 数据列表结束位置
:return:
"""
if low < high: # 至少有两个元素才进行
mid = (low + high) // 2 # 分割
merge_sort(data, low, mid) # 递归分割上一部分
merge_sort(data, mid + 1, high) # 递归分割下一部分
merge(data, low, mid, high) # 合并
if __name__ == '__main__':
import random
data_list = [1, 3, 21, 6, 50, 33, 34, 58, 66]
random.shuffle(data_list) # 打乱列表数据
print("pre:", data_list)
merge_sort(data_list, 0, len(data_list) - 1)
print("after:", data_list)
#结果：
#pre: [21, 3, 33, 58, 34, 66, 1, 6, 50]
#after: [1, 3, 6, 21, 33, 34, 50, 58, 66]
希尔排序
效率：与增量有关，O(n1+￡)其中<0￡<1,如增量为2k-1 复杂度为O(n3/2)
原理：
- 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。
- 先在各组内进行直接插入排序；
- 取第二个增量d2<d1重复上述的分组和排序，直至所取的增量 =1( < …<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
def shell_sort(data):
"""
希尔排序
:param data:待排序的数据列表
:return:
"""
d1 = len(data) // 2 # 设置分割大小为d1，
while d1 > 0:
for i in range(d1, len(data)):
tmp = data[i] # 当前分割元素位置
j = i - d1 # 上一个分割元素位置
while j >= 0 and tmp < data[j]: # 上一个元素分割位置比当前分割位置要大，则需要调整位置
data[j + d1] = data[j] # 后移动当前分割元素位置
j -= d1 # 往前移d1
data[j + d1] = tmp
d1 //= 2 # 继续分割
if __name__ == '__main__':
import random
data_list = [1, 3, 21, 6, 50, 33, 34, 58, 66]
random.shuffle(data_list) # 打乱列表数据
print("pre:", data_list)
shell_sort(data_list)
print("after:", data_list)
#结果：
#pre: [3, 66, 58, 34, 33, 50, 6, 21, 1]
#after: [1, 3, 6, 21, 33, 34, 50, 58, 66]
|