免费下载精神文明建设宣传网站,网站备案号 如何添加,域名怎么获得,php网站开发工程师职责快速排序#xff08;Quicksort#xff09;是一种常用的排序算法#xff0c;其基本思想是通过分治的策略将一个数组分成两个子数组#xff0c;然后分别对这两个子数组进行递归排序 一、快速排序算法的大致思路如下#xff1a;
1、我们在对列表进行排序的过程中#xff0c…快速排序Quicksort是一种常用的排序算法其基本思想是通过分治的策略将一个数组分成两个子数组然后分别对这两个子数组进行递归排序 一、快速排序算法的大致思路如下
1、我们在对列表进行排序的过程中当数组中只有一个列表元素进行排序最快。即不用排序。
所以我们在对列表进行快速排序的时候需要检查需要排序的列表是否只包含一个列表元素。若只包含一个列表元素则直接返回原来的列表即可。
2、当列表中存在多个列表元素的时候则需要我们对列表内容进行排序。这个排序过程即快速排序算法的核心函数名[小于参考值的列表元素][参考值]函数名[大于参考值的列表元素]。 二、解释快速排序算法的核心
我们需要先随便找一个列表元素作为参考值然后通过for循环和if语句的结合找到小于参考值的列表元素并将这些列表元素放置到一个新的列表中保存命名为less。同理找到大于参考值的列表元素用一个空的列表进行存储命名为greater。最后结合递归算法返回结果为从小到大排序将less的内容作为参数再次传入到快速排序算法函数中参考值将greater的内容作为参数再次传入到快速排序算法函数中。这样通过层层递归那么最后得到返回的结果就为一个有序的列表内容。 三、代码演示
从小到大排序效果具体实现代码如下
def quicksort(array): if len(array) 2: #判断列表中是否只有一个列表元素 return array else:pivot array[0] less [i for i in array[1:] if i pivot] #获取小于参考值的列表元素并将其保存在列表中 greater [i for i in array[1:] if i pivot] #获取大于参考值的列表元素并将其保存在列表中 return quicksort(less) [pivot] quicksort(greater) #通过递归实现排序功能
print(quicksort([10,5, 2, 5,5,6.54,3])) 从小到大排序效果具体实现代码如下只需要将凭借顺序修改即可函数名[大于参考值的列表元素][参考值]函数名[小于参考值的列表元素] def quicksort(array): if len(array) 2: #判断列表中是否只有一个列表元素 return array else:pivot array[0] less [i for i in array[1:] if i pivot] #获取小于参考值的列表元素并将其保存在列表中 greater [i for i in array[1:] if i pivot] #获取大于参考值的列表元素并将其保存在列表中 return quicksort(greater) [pivot] quicksort(less) #通过递归实现排序功能
print(quicksort([10,5, 2, 5,5,6.54,3]))四、快速排序算法执行过程(从小到大)
输入数据10 5 2 6
代码正常运行,输入列表内容不满足判断语句继续执行参考值10 第一次返回结果[5,2,6] 10[]
quicksort(less)第一次递归判断语句检测到[5,2,6] 不满足条件继续执行: 参考值5 第二次返回结果[2] 5 [6]
quicksort(less)第二次递归判断语句检测到[2]满足条件,返回2
quicksort(greater)第二次递归判断语句检测到[6]满足条件,返回6
参考值的左边结束递归后返回结果为[2,5,6]
参考值10
quicksort(greater)第一次递归判断语句检测[]满足条件返回结果[]
参考值的左边结束递归后返回结果为[]
最后全部递归执行完毕后将参考值左边列表内容参考值参考值右边列表内容返回得到最后的排序结果[2,5,6,10]
