快速排序
算法思想
快速排序算法首先会在序列中随机选择一个基准值(pivot),然后将除了基准值以外的数分为“比基准值小的数”和“比基准值大的数”这两个类别,再将其排列成以下形式:
[ 比基准值小] 基准值 [比基准值大]
接着,对两个“[ ]”中的数据进行排序之后,整体的排序便完成了。对“[ ]”里面的数据进行排序时同样也会使用快速排序,即使用递归的思想。
时间复杂度
时间复杂度$nlog_2(n)$
不稳定
Python代码实现
1 | def quick_sort(alist, first ,last): |
算法图解
1 | def quicksort(array): |