题解 | #排序#

https://blog.csdn.net/liangkaiping0525/article/details/82558188
转载
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
li[left] = li[right]
# 让左边游标往右移动，目的是找到大于mid的值，放到right游标位置
while left < right and li[left] < mid:
left += 1
li[right] = li[left]
# while结束后，把mid放到中间位置，left=right
li[left] = mid
# 递归处理左边的数据
quick_sort(li, start, left-1)
# 递归处理右边的数据
quick_sort(li, left+1, end)

关键点：
序列切割：
1、挑中间元素：mid = alist[start]
2、右推进：while right > left and alist[right] >= mid:
3、左推进：while left < right and alist[left] < mid:
4、推进循环：while left < right:
5、元素归位：alist[left] = mid
递归拆分：
1、小组边界确定：left = start、right = end
2、递归退出条件：if start < end:
3、函数自调用：quick_sort(alist, start, end)

时间复杂度
最优时间复杂度：O(nlogn)
对于每次快排，left和right的标签分别在左右两册数据全部都移动了一遍，相当于遍历了所有数据，那么时间复杂度是O(n)
因为涉及到了递归分组，所以他的时间复杂度是O(logn)
整体来说：最优的时间复杂度是 O(nlogn)

最坏时间复杂度：O(n2)
————————————————
版权声明：本文为CSDN博主「my_qq_990814268」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/liangkaiping0525/article/details/82558188

————————————————
版权声明：本文为CSDN博主「my_qq_990814268」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/liangkaiping0525/article/details/82558188