快速排序的非递归实现

题目描述
使用非递归方式实现快速排序算法。传统的快速排序通过递归调用处理子数组，而非递归实现需要使用栈（或队列）来模拟递归过程，手动管理待排序的子数组范围。

解题思路
非递归快速排序的核心思想是用显式的栈来替代系统调用栈。我们将每个待处理的子数组的起始和结束下标压入栈中，循环从栈中取出下标范围进行划分，直到栈为空。

步骤详解

1. 初始化栈

   • 创建一个栈（通常用数组或语言内置的栈结构），用于存储待排序子数组的起始下标（low）和结束下标（high）。
   • 初始时，将整个数组的范围（low = 0, high = n-1）压入栈。

2. 循环处理栈中的范围

   • 当栈不为空时，循环执行以下步骤：
     a. 从栈中弹出一个范围（low, high）。
     b. 如果 low >= high，说明当前子数组无需排序（元素个数 ≤ 1），跳过后续步骤，继续下一轮循环。
     c. 对当前子数组进行划分（Partition），得到基准元素的位置 pivotIndex。

3. 划分操作

   • 选择子数组的一个元素作为基准（例如，第一个元素、最后一个元素或随机元素）。
   • 重新排列数组，使得基准左侧的元素都不大于基准，右侧的元素都不小于基准。
   • 返回基准的最终位置 pivotIndex。

4. 压入新的子数组范围

   • 将基准左右两侧的子数组范围压入栈。注意：先压入较大的子数组范围可以减少栈的最大深度。
     • 若 (pivotIndex - low) < (high - pivotIndex)：
       • 先压入右侧范围 (pivotIndex + 1, high)
       • 再压入左侧范围 (low, pivotIndex - 1)
     • 否则：
       • 先压入左侧范围 (low, pivotIndex - 1)
       • 再压入右侧范围 (pivotIndex + 1, high)

5. 终止条件

   • 当栈为空时，所有子数组都已处理完毕，数组整体有序。

示例代码（Python）

def quick_sort_iterative(arr):
    if len(arr) <= 1:
        return arr
    
    stack = []
    low, high = 0, len(arr) - 1
    stack.append((low, high))
    
    while stack:
        low, high = stack.pop()
        if low >= high:
            continue
        
        pivot_index = partition(arr, low, high)
        
        # 判断左右子数组大小，先处理大的以减少栈深度
        left_size = pivot_index - low
        right_size = high - pivot_index
        
        if left_size < right_size:
            stack.append((pivot_index + 1, high))
            stack.append((low, pivot_index - 1))
        else:
            stack.append((low, pivot_index - 1))
            stack.append((pivot_index + 1, high))
    
    return arr

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

关键点

• 栈的使用替代了递归调用栈。
• 通过先处理较大的子数组，可以限制栈的最大深度为 O(log n)，避免最坏情况下栈溢出。
• 划分函数（partition）的实现与递归快速排序相同。

复杂度分析

• 时间复杂度：平均 O(n log n)，最坏 O(n²)（取决于划分平衡性）。
• 空间复杂度：O(log n)（栈空间），优于递归版的 O(log n) 系统栈空间，但实际使用显式栈。