内容简介:Python实现快速排序
快速 排序 采用了分治的思想,基本思想是选取数组中一个数为基准数(一般选择数组中的第一个数),一次排序过程中,将比基准数小的都放在它左侧,比基准数大的放在它的右侧。经过这次排序后得到两个数组和一个基准数,数组1中全部元素小于基准数,数组2中的全部元素大于基准数,然后对数组1,2分别进行同样的排序(递归),最后直到剩下一个数字。
下面给出 Python 代码实现
def partiton(li, low, high):
key = li[low]
while low < high:
while low < high and li[high] >= key:
high -= 1
if low < high:
li[low], li[high] = li[high], li[low]
while low < high and li[low] < key:
low += 1
if low < high:
li[high], li[low] = li[low], li[high]
return low
def quickSort(li, low, high):
if low >= high:
return
center = partiton(li, low, high)
quickSort(li, low, center - 1)
quickSort(li, center + 1, high)
关于实现:
快速排序的实现有很多种,这里我给出了比较常规并且好理解的一种.低位,高位两个指针从左右两侧相向遍历list。当高位指针发现了小于基准数的元素时,便停止移动,此时开始移动低位指针,当低位指针发现了大于基准数的元素时,便停止移动,两指针交换元素值,如此循环,直至两指针相遇。
关于时间复杂度:
快速排序具体的运行时间和原始列表本身的排序状态有很大关系,理论上快排的时间复杂度是(nlogn),但是如果运气不好糟糕,比如说初始列表是[5,4,3,2,1],那么根据上面的方法实现过程是什么样的呢,实现过程如下:
[5,4,3,2,1] -> [4,3,2,1,5] -> [3,2,1,4,5] -> [2,1,3,4,5] -> [1,2,3,4,5]
这样的排序实现过程很眼熟,跟最简单的冒泡排序的实现过程是完全相同的,所以说快排的最坏情况是冒泡排序,时间复杂度是(n 2 )
以上的实现较为通用,如果不使用python,而使用c++,java等其它编程语言实现,代码结构不会相差太多。我想到了一种比较贴合python语法特点,并且能较好的展示快排思想的实现方法。不同点是该方法时间在层递归中需要遍历2次列表,即复杂度为(2nlogn)
def qsort(lst):
if not lst:
return []
return qsort([i for i in lst[1:] if i < lst[0]]) + [lst[0]] + qsort([i for i in lst[1:] if i > lst[0]])
本文永久更新链接地址 : http://www.linuxidc.com/Linux/2018-01/150313.htm
以上所述就是小编给大家介绍的《Python实现快速排序》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
网络是怎样连接的
[日]户根勤 / 周自恒 / 人民邮电出版社 / 2017-1-1 / CNY 49.00
本书以探索之旅的形式,从在浏览器中输入网址开始,一路追踪了到显示出网页内容为止的整个过程,以图配文,讲解了网络的全貌,并重点介绍了实际的网络设备和软件是如何工作的。目的是帮助读者理解网络的本质意义,理解实际的设备和软件,进而熟练运用网络技术。同时,专设了“网络术语其实很简单”专栏,以对话的形式介绍了一些网络术语的词源,颇为生动有趣。 本书图文并茂,通俗易懂,非常适合计算机、网络爱好者及相关从......一起来看看 《网络是怎样连接的》 这本书的介绍吧!