Python实现快速排序的四种方式详解
本文详细解析了Python中快速排序的四种实现方式，包括一行代码的简洁写法、常见的双指针递归实现、《算法导论》版的分区逻辑以及基于栈的非递归迭代方案。文章深入探讨了原地排序对参数传递的要求，以及递归转迭代时栈结构的处理细节，帮助开发者全面理解快排核心机制。
快速排序概述
快速排序（Quick Sort）被广泛认为是最具实用价值的排序算法之一，其地位无可替代。目前主流编程语言的标准库中的排序函数，绝大多数底层均基于快速排序算法构建。
本文将以Python语言为例，系统介绍四种不同风格与实现思路的快速排序代码。
一行代码实现的简洁版本
第一种实现方式：利用一行代码完成的简洁版本
quick_sort = lambda array: array if len(array) <= 1 else quick_sort([item for item in array[1:] if item <= array[0]]) + [array[0]] + quick_sort([item for item in array[1:] if item > array[0]])
常见的快排实现
第二种实现方式：网络中常见的标准快排实现
def quick_sort(array, left, right):
if left >= right:
return
low = left
high = right
key = array[low]
while left < right:
while left < right and array[right] > key:
right -= 1
array[left] = array[right]
while left < right and array[left] <= key:
left += 1
array[right] = array[left]
array[right] = key
quick_sort(array, low, left - 1)
quick_sort(array, left + 1, high)
需要明确的是，快速排序属于原地排序算法，因此无需返回新的数组对象。
若直接传入列表，虽可通过len()获取长度，但在递归过程中若使用切片操作，会触发原列表的复制行为，从而违背原地排序的设计初衷。因此，正确的做法是显式传递数组的上边界和下边界索引。
《算法导论》中的快排程序
第三种实现方式：参考《算法导论》的快排程序
def quick_sort(array, l, r):
if l < r:
q = partition(array, l, r)
quick_sort(array, l, q - 1)
quick_sort(array, q + 1, r)
def partition(array, l, r):
x = array[r]
i = l - 1
for j in range(l, r):
if array[j] <= x:
i += 1
array[i], array[j] = array[j], array[i]
array[i + 1], array[r] = array[r], array[i+1]
return i + 1
该版本与前者的主要区别在于分区（Partition）过程的实现逻辑。此版本仅使用单层循环，且能在单次遍历中完成分区操作，相比之下代码更为精简高效。
非递归快排程序实现
第四种实现方式：基于栈的非递归快排程序
在深入代码之前，先澄清关于“栈”的概念。通常意义上的栈包含两层含义：一是作为后进先出（LIFO）的数据结构，二是函数调用时的内存栈。本质上，函数内存栈的结构就是一个后进先出的栈。在汇编层面，函数调用时会修改堆栈指针寄存器ESP，它指向局部栈的栈顶；而EBP寄存器则保存栈底地址。至于与栈空间相对的堆空间，其组织形式是否也为完全二叉树，尚存探讨空间。
在高级语言中，将递归逻辑转换为迭代实现时，核心在于模拟栈的行为，需重点解决两个问题：
1. 栈中应当存储哪些数据？
2. 迭代终止的条件是什么？
栈中存储的必然是需要继续处理的函数参数。对于快速排序而言，迭代的核心参数是数组的上边界low和下边界high。因此，迭代结束的条件即为low等于high。
def quick_sort(array, l, r):
if l >= r:
return
stack = []
stack.append(l)
stack.append(r)
while stack:
low = stack.pop(0)
high = stack.pop(0)
if high - low <= 0:
continue
x = array[high]
i = low - 1
for j in range(low, high):
if array[j] <= x:
i += 1
array[i], array[j] = array[j], array[i]
array[i + 1], array[high] = array[high], array[i + 1]
stack.extend([low, i, i + 2, high])
此外需注意语言差异：在C++、Java等语言中，访问下标-1会引发错误；而在Python中，负数索引表示从末尾开始计数，访问最后一个元素。这意味着若程序逻辑有误，Python可能不会报错而是输出错误结果，其他语言则直接抛出异常。
以上即为Python实现快速排序算法的四种方式详解，希望能对读者有所帮助。如有任何疑问，欢迎留言交流，小编将及时回复。同时感谢大家对本网站的支持！
免责声明：本文内容仅供参考，不代表本站观点。转载或引用请注明出处。
