快速排序的四种python实现（推荐）

2023-08-25 02:54:04 75

快速排序算法，简称快排，是最实用的排序算法，没有之一，各大语言标准库的排序函数也基本都是基于快排实现的。

本文用python语言介绍四种不同的快排实现。

1.一行代码实现的简洁版本

quick_sort=lambdaarray:arrayiflen(array)<=1elsequick_sort([itemforiteminarray[1:]ifitem<=array[0]])+[array[0]]+quick_sort([itemforiteminarray[1:]ifitem>array[0]])

2.网上常见的快排实现

defquick_sort(array,left,right):
ifleft>=right:
return
low=left
high=right
key=array[low]
whileleftkey:
right-=1
array[left]=array[right]
whileleft
由于快排是原地排序，因此不需要返回array。
array如果是个列表的话，可以通过len(array)求得长度，但是后边递归调用的时候必须使用分片，而分片执行的原列表的复制操作，这样就达不到原地排序的目的了，所以还是要传上边界和下边界的。
3.《算法导论》中的快排程序
defquick_sort(array,l,r):
ifl
这个版本跟上个版本的不同在于分片过程不同，只用了一层循环，并且一趟就完成分片，相比之下代码要简洁的多了。
4.用栈实现非递归的快排程序
先说两句题外话，一般意义上的栈有两层含义，一层是后进先出的数据结构栈，一层是指函数的内存栈，归根结底，函数的内存栈的结构就是一个后进先出的栈。汇编代码中，调用一个函数的时候，修改的也是堆栈指针寄存器ESP，该寄存器保存的是函数局部栈的栈顶，另外一个寄存器EBP保存的是栈底。不知道与栈存储空间相对的堆存储空间，其组织结构是否也是一个完全二叉树呢？
高级语言将递归转换为迭代，用的也是栈，需要考虑两个问题:
1）栈里边保存什么？
2）迭代结束的条件是什么？
栈里边保存的当然是需要迭代的函数参数，结束条件也是跟需要迭代的参数有关。对于快速排序来说，迭代的参数是数组的上边界low和下边界high，迭代结束的条件是low==high。


defquick_sort(array,l,r):
ifl>=r:
return
stack=[]
stack.append(l)
stack.append(r)
whilestack:
low=stack.pop(0)
high=stack.pop(0)
ifhigh-low<=0:
continue
x=array[high]
i=low-1
forjinrange(low,high):
ifarray[j]<=x:
i+=1
array[i],array[j]=array[j],array[i]
array[i+1],array[high]=array[high],array[i+1]
stack.extend([low,i,i+2,high])

另外，当数组下标为-1时，C++、Java等语言中会报错，但python中访问的是最后一个元素，所以如果程序写错了，可能其他语言会报错，但python会输出一个错误的结果。
以上所述是小编给大家介绍的python实现快速排序算法详解整合，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对毛票票网站的支持！
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

快速排序的四种python实现（推荐）

热门推荐

随机推荐