Python是否存在无需递归的快速排序实现？

本实现采用栈替代递归调用栈，完全无递归逻辑，支持原地排序一维Python列表/Numpy数组，可直接适配Numba GPU编译要求。

核心逻辑 #

• 用栈存储待排序子数组的左右边界索引，替代递归的系统栈
• 每次弹出一组边界，完成分区操作后，将生成的两个未排序子数组边界压入栈
• 重复上述操作直到栈为空，全数组排序完成
• 全程原地修改数组，无额外大内存申请，适合GPU显存受限场景

可直接适配Numba的实现代码 #

Lomuto分区逻辑实现简单，无额外复杂操作，更适合Numba GPU编译优化：

def partition(arr, low, high):
    # 取最右侧元素为基准值
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def quicksort_iterative(arr):
    # 兼容Python列表、Numpy数组输入
    n = len(arr)
    # 初始化栈，存储子数组的左右边界索引
    stack = []
    # 初始压入全数组的边界
    stack.append((0, n - 1))
    
    # 栈非空则循环处理
    while stack:
        low, high = stack.pop()
        # 分区得到基准值的位置
        pi = partition(arr, low, high)
        # 左子数组有未排序元素则压入栈
        if pi - 1 > low:
            stack.append((low, pi - 1))
        # 右子数组有未排序元素则压入栈
        if pi + 1 < high:
            stack.append((pi + 1, high))
    return arr

Numba GPU适配优化建议 #

如果需要放到Numba CUDA环境运行，可做如下修改：

• 给两个函数添加@numba.njit装饰器即可在CPU侧加速，添加@numba.cuda.jit可适配GPU kernel逻辑
• GPU环境下建议预先固定栈的最大长度（一般设为数组长度的2倍即可覆盖所有场景），避免列表动态扩容的编译问题
• 分区逻辑可根据GPU线程布局调整基准值选择策略，进一步提升并行效率

测试示例 #

import numpy as np
# 测试Numpy数组
arr_np = np.array([10, 7, 8, 9, 1, 5])
quicksort_iterative(arr_np)
print(arr_np) # 输出 [ 1  5  7  8  9 10]

# 测试Python列表
arr_list = [10, 7, 8, 9, 1, 5]
quicksort_iterative(arr_list)
print(arr_list) # 输出 [1, 5, 7, 8, 9, 10]

内容的提问来源于stack exchange，提问作者Edy Bourne