quicksort

quicksort.py

def quick_sort_iterative(arr):  
    stack = [(0, len(arr) - 1)]  # 定义一个栈，用于存储待排序的区间  

    while stack:  
        start, end = stack.pop()  # 从栈中弹出一个区间  
        if start >= end:  
            continue  
        
        pivot = arr[end]  # 选择最后一个元素作为枢轴  
        partition_index = start  # 分区的索引  
        
        for i in range(start, end):  
            if arr[i] < pivot:  
                arr[i], arr[partition_index] = arr[partition_index], arr[i]  # 交换  
                partition_index += 1  
        
        arr[partition_index], arr[end] = arr[end], arr[partition_index]  # 将枢轴放到正确的位置  
        
        # 将新的区间添加到栈中  
        stack.append((start, partition_index - 1))  # 左区间  
        stack.append((partition_index + 1, end))    # 右区间  

# 示例用法  
arr = [3, 6, 8, 10, 1, 2, 1]  
quick_sort_iterative(arr)  
print("排序后的数组:", arr)