后端开发|Python教程
Python,数据结构,算法,快速排序
后端开发-Python教程
c 建站源码,ubuntu 桌面与命令,爬虫神经网络,用php编写一个比较大的函数,漳州必应seolzw
A、概述
抓娃娃码支付源码,ubuntu分区全部删除,防止爬虫的网站,php7与php5.5,徐州谷歌seolzw
快速排序（quick sort）是一种分治排序算法。该算法首先 选取 一个划分元素（partition element，有时又称为pivot）；接着重排列表将其 划分 为三个部分：left（小于划分元素pivot的部分）、划分元素pivot、right（大于划分元素pivot的部分），此时，划分元素pivot已经在列表的最终位置上；然后分别对left和right两个部分进行 递归排序。
梦网网站源码,ubuntu 聊天室,tomcat正在摧毁处理器,python网络爬虫监狱,php单继承可以使用,seo与404lzw
其中，划分元素的 选取 直接影响到快速排序算法的效率，通常选择列表的第一个元素或者中间元素或者最后一个元素作为划分元素，当然也有更复杂的选择方式；划分 过程根据划分元素重排列表，是快速排序算法的关键所在，该过程的原理示意图如下：
快速排序算法的优点是：原位排序（只使用很小的辅助栈），平均情况下的时间复杂度为 O(n log n)。快速排序算法的缺点是：它是不稳定的排序算法，最坏情况下的时间复杂度为 O(n2)。
B、Python实现
1、标准实现
#!/usr/bin/env python# -*- coding: utf-8 -*-def stdQuicksort(L): qsort(L, 0, len(L) - 1)def qsort(L, first, last): if first < last: split = partition(L, first, last) qsort(L, first, split - 1) qsort(L, split + 1, last)def partition(L, first, last): # 选取列表中的第一个元素作为划分元素 pivot = L[first] leftmark = first + 1 rightmark = last while True: while L[leftmark] pivot:# 这里不需要检测，划分元素pivot是列表中的最小元素时，# rightmark会自动停在first处rightmark -= 1 if leftmark < rightmark:# 此时，leftmark处的元素大于pivot， #而rightmark处的元素小于等于pivot，交换二者L[leftmark], L[rightmark] = L[rightmark], L[leftmark] else:break # 交换first处的划分元素与rightmark处的元素 L[first], L[rightmark] = L[rightmark], L[first] # 返回划分元素pivot的最终位置 return rightmark
2、Pythonic实现
#!/usr/bin/env python# -*- coding: utf-8 -*-def pycQuicksort(L): if len(L) <= 1: return L return pycQuicksort([x for x in L if x L[0]])
对比 标准实现 可以看出，Pythonic实现 更简洁、更直观、更酷。但需要指出的是，Pythonic实现 使用了Python中的 列表解析 （List Comprehension，也叫列表展开、列表推导），每一次 递归排序 都会产生新的列表，因此失去了快速排序算法本来的 原位排序 的优点。
C、算法测试
#!/usr/bin/env python# -*- coding: utf-8 -*-if __name__ == \__main__: L = [54, 26, 93, 17, 77, 31, 44, 55, 20] M = L[:] print(efore stdQuicksort: + str(L)) stdQuicksort(L) print(after stdQuicksort: + str(L)) print(efore pycQuicksort: + str(M)) print(after pycQuicksort: + str(pycQuicksort(M)))
运行结果：
$ python testquicksort.pybefore stdQuicksort: [54, 26, 93, 17, 77, 31, 44, 55, 20]after stdQuicksort: [17, 20, 26, 31, 44, 54, 55, 77, 93]before pycQuicksort: [54, 26, 93, 17, 77, 31, 44, 55, 20]after pycQuicksort: [17, 20, 26, 31, 44, 54, 55, 77, 93]
如果觉得《Python实现的数据结构与算法之快速排序详解》对你有帮助，请点赞、收藏，并留下你的观点哦！
