代码拉取完成,页面将自动刷新
同步操作将从 陌溪/LearningNotes 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
快速排序也是分治的思想,但是它于归并算法更加好,是因为归并算法会用到辅助数组,其空间复杂度为O(n),而快速排序不需要用到新的数组空间,它的空间复杂度是O(1)
快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。具体算法描述如下:
def quick_sort(li, start, end):
# 分治 一分为二
# start=end ,证明要处理的数据只有一个
# start>end ,证明右边没有数据
if start >= end:
return
# 定义两个游标,分别指向0和末尾位置
left = start
right = end
# 把0位置的数据,认为是中间值
mid = li[left]
while left < right:
# 让右边游标往左移动,目的是找到小于mid的值,放到left游标位置
while left < right and li[right] >= mid:
right -= 1
print("left 1", li)
li[left] = li[right]
print("left 2", li)
# 让左边游标往右移动,目的是找到大于mid的值,放到right游标位置
while left < right and li[left] < mid:
left += 1
li[right] = li[left]
print("right ", li)
# while结束后,把mid放到中间位置,left=right
li[left] = mid
# 递归处理左边的数据
quick_sort(li, start, left-1)
# 递归处理右边的数据
quick_sort(li, left+1, end)
if __name__ == '__main__':
l = [1,5,4,6,2,8]
# l = 3 [2,1,5,6,5,4]
# [2, 1, 5, 6, 5, 4]
quick_sort(l,0,len(l)-1)
print(l)
# 稳定性:不稳定
# 最优时间复杂度:O(nlogn)
# 最坏时间复杂度:O(n^2)
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。