python排序算法——快速排序（附代码）-创新互联
- python排序算法——快速排序
- 一、前言
- 二、算法描述
- 三、代码实现
- 总结
一、前言
相关知识来自《python算法设计与分析》。初级排序算法是指几种较为基础且容易理解的排序算法。初级排序算法包括插入排序、选择排序和冒泡排序3种。相比起初级排序算法，高级排序算法往往有更加复杂的逻辑，但也会有更高的时间或空间效率。其中有些高级排序算法是由初级排序算法优化而来的。本文介绍快速排序。
二、算法描述快速排序的思想是：取数组中的一个数作为基准值，把所有小于基准值的数都放在它的一侧，再把所有大于基准值的数都放在它的另一侧。随后，对基准值左右两侧的数组分别进行快速排序。由此可以看出，快速排序的整个排序过程也是递归进行的。
快速排序的平均时间复杂度是O(nlgn)，最好情况下的时间复杂度是O(nlgn)。最坏情况下，快速排序的时间复杂度可能退化成O( n2 )，但这种情况很少见。它的空间复杂度是O(nlgn)。它是一个不稳定的排序算法。如果使用得当，快速排序的速度可以达到归并排序和堆排序的数倍，所以快速排序是一种极其常用的算法。
快速排序的流程如图2-22所示（以升序排序为例）。
一般情况下，我们取数组的第一个数作为基准进行快速排序。在第一步中，基准数为5。可以看出，在第二行的数组中，比5小的元素：3、4、1、2，都被置于5的左侧，而比5大的元素则被置于5的右侧。这时，元素5在有序数组中的位置就确定了。第三行中，我们再取左右两个无序数组的第一个数3和6，分别作为它们的基准数，然后再次对数组进行分拆。分拆结束之后，3和6在有序数组中的位置也确定了。接下来，继续处理分拆出来的4个子数组：[1,2]、[4]、[]、[8,7]。其中，一个子数组只剩一个数，一个为空。这意味着[4]与[]已经完成了对自己的快速排序。而其他的两个子数组则需继续处理。全部处理完毕后，我们将得到一个完整的有序数组。
可以看出，快速排序也是通过这样的分治思想来排序的。
三、代码实现在QuickSort()函数中，首先是边界条件：如果传入函数的列表长度小于等于1，那么这一段列表必定是有序的，可以直接返回。如果不满足边界条件，则继续执行函数。先用key存储基准值，再定义3个列表存储小于基准数的元素llist，大于基准数的元素rlist和等于基准数的元素mlist。由于接下来for循环的范围不包括列表中的第一个数，所以对mlist初始化时，多加一个初始元素key。
接下来的for循环把数组内的元素分别归入3个列表中。随后，再次调用QuickSort()函数，对llist和rlist进行排序。这样，llist和rlist就是有序的了，而mlist内的元素刚好处于它们中间的连接部分。所以，排序完成后，把llist、mlist、rlist按顺序拼接到一起并输出。
快速排序代码（基础版）：
nums = [5,3,6,4,1,2,8,7]
def QuickSort(num):
if len(num)<= 1: #边界条件
return num
key = num[0] #取数组的第一个数为基准数
llist,rlist,mlist = [],[],[key] #定义空列表，分别存储小于/大于/等于基准数的元素
for i in range(1,len(num)): #遍历数组，把元素归类到3个列表中
if num[i] >key:
rlist.append(num[i])
elif num[i]< key:
llist.append(num[i])
else:
mlist.append(num[i])
return QuickSort(llist)+mlist+QuickSort(rlist) #对左右子列表快排，拼接3个列表并返回
print(QuickSort(nums))
运行程序，输出结果为：
[1,2,3,4,5,6,7,8]总结
以上就是本文要讲的内容，本文介绍了快速排序理论知识和代码实现，快速排序的平均时间复杂度是O(nlgn)，最好情况下的时间复杂度是O(nlgn)。最坏情况下，快速排序的时间复杂度可能退化成O( n2 )，但这种情况很少见。它的空间复杂度是O(nlgn)。它是一个不稳定的排序算法。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
网页名称：python排序算法——快速排序（附代码）-创新互联
本文地址：http://myzitong.com/article/pgshj.html