python快速排序的运作过程-Python教程-PHP中文网

python快速排序的运作过程

冷炫風刃

发布： 2025-10-30 22:42:02

原创

573人浏览过

快速排序通过分治法将数组按基准值划分为两部分并递归排序。首先选择基准（如末尾元素1），分区后小元素在左、大元素在右，如[3,6,8,10,1,2,1]变为[1,1,2,10,6,8,3]。接着对左右子数组递归执行快排，直到子数组长度为0或1。算法平均时间复杂度O(n log n)，最坏O(n²)，常用原地分区提升效率。

python快速排序的运作过程

快速排序是一种高效的排序算法，通过“分治”的思想把一个大问题拆成小问题来解决。它的核心思路是选一个基准值（pivot），把数组分成两部分：小于基准的放左边，大于基准的放右边，然后对左右两部分递归处理。整个过程不需要额外的存储空间，属于原地排序。

选择基准与分区操作

排序开始时，从数组中选一个元素作为基准（通常选第一个、最后一个或中间元素）。然后遍历整个数组，将比基准小的元素移到左边，比基准大的移到右边。这个过程叫“分区”（partition）。

例如数组 [3, 6, 8, 10, 1, 2, 1]，如果选最后一个元素 1 为基准，经过分区后可能变成 [1, 1, 2, 10, 6, 8, 3]，此时基准 1 已经在正确位置上。

递归处理子数组

分区完成后，基准左边和右边的子数组仍然是无序的。接下来对这两个子数组分别进行同样的快速排序操作：

立即学习“Python免费学习笔记（深入）”；

对左半部分递归调用快排
对右半部分递归调用快排

递归直到子数组长度为0或1时停止，这时整个数组就有序了。

简篇AI排版

AI排版工具，上传图文素材，秒出专业效果！

134

查看详情

代码实现简要说明

一个简单的实现方式如下：

def quicksort(arr):
   if len(arr)       return arr
   pivot = arr[len(arr) // 2]
   left = [x for x in arr if x < pivot]
   middle = [x for x in arr if x == pivot]
   right = [x for x in arr if x > pivot]
   return quicksort(left) + middle + quicksort(right)

这段代码虽然清晰易懂，但使用了额外的空间。实际应用中常采用原地分区的方式（如Hoare或Lomuto分区方案）提升效率。

基本上就这些。快排平均时间复杂度是 O(n log n)，最坏情况是 O(n²)，但在合理选择基准的情况下表现非常优秀。

以上就是python快速排序的运作过程的详细内容，更多请关注php中文网其它相关文章！