python列表快速排序_python 实现快速排序

一、快排思想

快速排序可以理解为是对冒泡排序的一种改进，把一组数，按照初始选定的标杆（参照数），

分别从两端开始排序，左端'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)

最后

以上就是酷酷玉米为你收集整理的python列表快速排序_python 实现快速排序的全部内容，希望文章能够帮你解决python列表快速排序_python 实现快速排序所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。