首页 / 算法 / 快速排序 python 代码实现
快速排序 python 代码实现
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了快速排序 python 代码实现,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1415字,纯文字阅读大概需要3分钟。
内容图文
![快速排序 python 代码实现](/upload/InfoBanner/zyjiaocheng/770/5b69c06c98184282bdcde9aac2834f70.jpg)
原理:
快速排序(Quicksort)是对冒泡排序的一种改进。
快速排序由C. A. R. Hoare在1960年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
?? 快速排序:是给基准数据找其正确索引位置的过程.
?? 假设最开始的基准数为数组第一个元素,则首先用一个临时变量去存储基准数,即tmp;然后分别从数组的两端扫描数组,设两个指示标志:low指向起始位置,high指向末尾.
首先确定一个基准数:例如下图的基准数一般都是设置第一个数,基准数tmp=49 ,基准数在与剩下的n-1的部分进行,从最后一个数比较,若基准数小于进行交换,否者大于或者等于基准数不进行交换。此时将基准数与倒数第二个数进行比较27小于49,27和49进行交换。然后基准数49与第二数进行比较,若基准数=49大于第二个数38不交换,再与第三个数比较49<65 ,进行交换,以此类推,如下图
使用python 代码实现:
def quick_sort(data):
"""quick_sort"""
if len(data) >= 2:
mid = data[len(data)//2]
left,right = [], []
data.remove(mid)
for num in data:
if num >= mid:
right.append(num)
else:
left.append(num)
return quick_sort(left) + [mid] + quick_sort(right)
else:
return data
a = [2,3,4,1,45,6,6,7,8,7,9,10,18,20,30,12]
结果:
print(quick_sort(a))
[1, 2, 3, 4, 6, 6, 7, 7, 8, 9, 10, 12, 18, 20, 30, 45]
小结:
时间复杂度:
最好情况(待排序列接近无序)时间复杂度为O(nlog2n)
最坏情况(待排序列接近有序)时间复杂度为O(n2)
平均时间复杂度为O(nlog2n)。
内容总结
以上是互联网集市为您收集整理的快速排序 python 代码实现全部内容,希望文章能够帮你解决快速排序 python 代码实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。