谢尔排序是将数据一分为二的不断递归,让分开的两部分位置相对应的两个值比较大小,从而达到每个部分都是相对的顺序排列,而归并排序是分治策略,分为分裂和合并两个过程。耗费了额外的存储空间。
def mergesort(alist):
if len(alist) > 1:
mid = len(alist) // 2
lefthalf = alist[:mid]
righthalf = alist[mid:]
mergesort(lefthalf) # 递归过程
mergesort(righthalf)
i = j = k = 0
while i < len(lefthalf) and j < len(righthalf):
if lefthalf[i] < righthalf[j]: # 分裂后选择较小的值,放入临时列表
alist[k] = lefthalf[i]
i += 1
else:
alist[k] = righthalf[j]
j += 1
k += 1
while i < len(lefthalf): # 左侧一半的长度大于右侧,需单独进行合并步骤
alist[k] = lefthalf[i]
i += 1
k += 1
while j < len(righthalf):
alist[k] = righthalf[j]
j += 1
k += 1
print('Merging', alist)
mergesort([9, 8, 7, 6, 5, 4, 3, 2, 1])
def merge_sort(lst):
if len(lst) <= 1:
return lst
middle = len(lst) // 2
left = merge_sort(lst[:middle])
right = merge_sort(lst[middle:])
merged = []
while left and right:
if left[0] <= right[0]:
merged.append(left.pop(0))
else:
merged.append(right.pop(0))
merged.extend(right if right else left) # 在尾部添加多出部分
return merged
print(merge_sort([9, 8, 7, 6, 5, 4, 3, 2]))
# 时间复杂度O(logn)
# 归并过程复杂度为O(n)
# 综合考虑O(nlogn)
快速排序,依据一个中值把数据表分为两半,然后对每一部分进行快速排序。影响因素为中值的选择。主要是依靠游标的移动,来达到排序的目的。代码内有两部分交换,一部分是前后游标位置的大小判断,产生的交换,另一次为游标相遇后,将首项人为选定的中值交换到中间位置。
def quick_sort(alist):
quick_sort_helper(alist, 0, len(alist)-1)
def quick_sort_helper(alist, first, last):
if first < last:
split_point = partition(alist, first, last)
quick_sort_helper(alist, first, split_point-1) # 递归
quick_sort_helper(alist, split_point+1, last)
def partition(alist, first, last):
pivotvalue = alist[first] # 定义中位值,假设第一个值既是中位值
leftmark = first + 1 # 左侧值从第二个值开始比较
rightmark = last # 右侧值从最后一个开始比较
done = False
while not done:
while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
leftmark += 1 # 判断左侧值小于中位值
while rightmark >= leftmark and alist[rightmark] >= pivotvalue:
rightmark -= 1
if rightmark < leftmark:
done = True
else:
alist[leftmark], alist[rightmark] = alist[rightmark], alist[leftmark]
alist[first], alist[rightmark] = alist[rightmark], alist[first]
return rightmark
alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
quicksort(alist)
print(alist)
# 分裂复杂度O(logn)
# 中值选取的可能会是O(n²)
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。