使用python实现四种快速排序-创新互联
这篇文章给大家分享的是有关使用python实现四种快速排序的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。
成都创新互联公司长期为近1000家客户提供的网站建设服务,团队从业经验10年,关注不同地域、不同群体,并针对不同对象提供差异化的产品和服务;打造开放共赢平台,与合作伙伴共同营造健康的互联网生态环境。为兴安盟乌兰浩特企业提供专业的网站建设、成都网站制作,兴安盟乌兰浩特网站改版等技术服务。拥有10多年丰富建站经验和众多成功案例,为您定制开发。快速排序算法,简称快排,是最实用的排序算法,没有之一,各大语言标准库的排序函数也基本都是基于快排实现的。
1. 一行代码实现的简洁版本
quick_sort = lambda array: array if len(array) <= 1 else quick_sort([item for item in array[1:] if item <= array[0]]) + [array[0]] + quick_sort([item for item in array[1:] if item > array[0]])
2. 网上常见的快排实现
def quick_sort(array, left, right): if left >= right: return low = left high = right key = array[low] while left < right: while left < right and array[right] > key: right -= 1 array[left] = array[right] while left < right and array[left] <= key: left += 1 array[right] = array[left] array[right] = key quick_sort(array, low, left - 1) quick_sort(array, left + 1, high)
由于快排是原地排序,因此不需要返回array。
array如果是个列表的话,可以通过len(array)求得长度,但是后边递归调用的时候必须使用分片,而分片执行的原列表的复制操作,这样就达不到原地排序的目的了,所以还是要传上边界和下边界的。
3.《算法导论》中的快排程序
def quick_sort(array, l, r): if l < r: q = partition(array, l, r) quick_sort(array, l, q - 1) quick_sort(array, q + 1, r) def partition(array, l, r): x = array[r] i = l - 1 for j in range(l, r): if array[j] <= x: i += 1 array[i], array[j] = array[j], array[i] array[i + 1], array[r] = array[r], array[i+1] return i + 1
这个版本跟上个版本的不同在于分片过程不同,只用了一层循环,并且一趟就完成分片,相比之下代码要简洁的多了。
4. 用栈实现非递归的快排程序
先说两句题外话,一般意义上的栈有两层含义,一层是后进先出的数据结构栈,一层是指函数的内存栈,归根结底,函数的内存栈的结构就是一个后进先出的栈。汇编代码中,调用一个函数的时候,修改的也是堆栈指针寄存器ESP,该寄存器保存的是函数局部栈的栈顶,另外一个寄存器EBP保存的是栈底。不知道与栈存储空间相对的堆存储空间,其组织结构是否也是一个完全二叉树呢?
高级语言将递归转换为迭代,用的也是栈,需要考虑两个问题:
1)栈里边保存什么?
2)迭代结束的条件是什么?
栈里边保存的当然是需要迭代的函数参数,结束条件也是跟需要迭代的参数有关。对于快速排序来说,迭代的参数是数组的上边界low和下边界high,迭代结束的条件是low == high。
def quick_sort(array, l, r): if l >= r: return stack = [] stack.append(l) stack.append(r) while stack: low = stack.pop(0) high = stack.pop(0) if high - low <= 0: continue x = array[high] i = low - 1 for j in range(low, high): if array[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实现四种快速排序”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,让大家可以学到更多知识,如果觉得文章不错,可以把它分享出去让更多的人看到吧!
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
网站标题:使用python实现四种快速排序-创新互联
本文网址:http://hbruida.cn/article/cecdps.html