排序算法（持续更新…）
106 浏览量
2020-12-21
11:32:05
上传
评论
收藏 30KB PDF 举报
排序算法（持续更新排序算法（持续更新…））
排序算法排序算法快速排序（参考百度百科）并归排序
快速排序（参考百度百科）快速排序（参考百度百科）
def quick_sort(data):
if len(data) >= 2:
left,right=[],[] mid=data[len(data)//2] data.remove(mid)#记得先将列表中的数去除否则将无限迭代
for num in data:
if(num<=mid):
left.append(num)
else:
right.append(num)
return quick_sort(left)+[mid]+quick_sort(right)
else:
return data
array = [2,3,5,7,1,4,6,15,5,2,7,9,10,15,9,17,12] print(quick_sort(array))
最理想的情况下（每次都二等分），则时间复杂度为O(nlogn)。
最坏情况下（每次中间数都是最大/最小），时间复杂度为O(n²)
快速排序的平均时间复杂度也是O(nlogn)，空间复杂度O(1)
并归排序并归排序
def mergesort(lists):
if len(lists)<=1:
return lists
mid = len(lists)//2
left=mergesort(lists[:mid])
right=mergesort(lists[mid:])
return merge(left,right)
def merge(left,right):
l,r=0,0
result=[] while(l<len(left) and r<len(right)):
if(left[l]<right[r]):
result.append(left[l])
l+=1
else:
result.append(right[r])
r+=1
result+=left[l:] result+=right[r:] return result
print(mergesort([9,2,3,4,7,6,8,1,5,0]))
时间复杂度O(nlogn)，空间复杂度O(n)
特别需要注意的是，在敲代码过程中一定要注意停止判断，即：当列表长度为特别需要注意的是，在敲代码过程中一定要注意停止判断，即：当列表长度为1时，停止迭代！！！（特别容易忘）时，停止迭代！！！（特别容易忘）
在做题时发现并归排序比快排慢好多，到底在什么情况下，并归更快，以后测试一下
作者：dinosaurcity
weixin_38661128
- 粉丝: 4
- 资源: 887
评论0