一、快排思想
快速排序可以理解为是对冒泡排序的一种改进，把一组数，按照初始选定的标杆（参照数），
分别从两端开始排序，左端'i'只要小于标杆（参照数）的数，右端'j'只要大于标杆（参照数）的数，
i----->middle<-----j 每一次排序循环条件为 i != j 左端 i 不等于右端 j，
每次排序，右端j先排，从右往左找，直到找到第一个比标杆（参照数）小的数就停下来。
而 i 从左往右，除了找到比自己大的数停下来之外，还要满足i
当i和j都停下来时，我们就交换索引i处的值和索引j处的值，如果 i != j 就继续从当前j往左边排序找到比标杆（参照值）小的数，
i继续从当前位置向右找比自己大的数，这样循环直到 i == j 意味着，当前i、j索引的值，除了参照值左边都比标杆（参照数）小，
右边都比参照数大，然后第一次排序把标杆和i处的值交换，就算完成了，
然后把该数组分成了两段，分别再递归调用自身继续排序，直到每轮剩下两个数或者 j 先找，走到了 i 的位置，所以递归调用停止的条件就应该是 i>j-1。
二、python 实现
def quickSort(list, start, end):
if start>end:
return
i, j = start, end
flag = list[start]
while True:
#先从右往左找
while j>i and list[j] >= flag:
j = j - 1
#再从左往右找
while i< j and list[i] <= flag:
i += 1
if i < j:
list[i], list[j] = list[j], list[i]
elif i == j:
#当左右相等时第一次递归结束
list[start], list[i] = list[i], list[start]
break
quickSort(list,start, i-1)
quickSort(list, i+1, end)
list_test = [7, 4, 7, 2, 4,19, 10, 4, 9, 5, 8, 10]
print(list_test)
quickSort(list_test, 0, (len(list_test)-1))
print(list_test)
#结果为：
[7, 4, 7, 2, 4, 19, 10, 4, 9, 5, 8, 10]
[2, 4, 4, 4, 5, 7, 7, 8, 9, 10, 10, 19]
大同小异,这样写
def quick_sort(ql,start, end):
if start > end:
return
mark = ql[start]
i, j = start, end
while i
while i= mark:
j -= 1
while i
i += 1
ql[i], ql[j] = ql[j], ql[i]
ql[start], ql[i] = ql[i], ql[start]
quick_sort(ql,start, i-1)
quick_sort(ql, i+1, end)
本文链接：https://my.lmcjl.com/post/5094.html
4 评论