递归快速排序时获取完整列表状态以实现GUI可视化

你的现有快速排序实现是非原地排序，每次递归都会生成新的子列表并最终合并，这种方式无法追踪原始完整列表的状态变化——因为子列表只是原列表的片段，合并前没有修改原列表，自然拿不到全局状态。要实现需求，需要改成原地快速排序，在原列表上直接操作，同时记录每一步的完整状态。

修改后的实现代码 #

class QuickSortVisualizer:
    def __init__(self, data):
        self.data = data.copy()  # 保留原始数据，避免修改输入
        self.state_log = []  # 用于保存每一步的完整列表状态

    def partition(self, low, high):
        pivot = self.data[high]
        i = low - 1  # 小于基准的元素的最后位置索引

        for j in range(low, high):
            if self.data[j] <= pivot:
                i += 1
                # 交换元素
                self.data[i], self.data[j] = self.data[j], self.data[i]
                # 记录交换后的完整状态
                self.state_log.append(self.data.copy())
        
        # 将基准元素放到正确位置
        self.data[i+1], self.data[high] = self.data[high], self.data[i+1]
        # 记录基准归位后的完整状态
        self.state_log.append(self.data.copy())
        return i + 1

    def quick_sort(self, low=0, high=None):
        if high is None:
            high = len(self.data) - 1
        
        if low < high:
            pi = self.partition(low, high)
            # 递归排序左半部分
            self.quick_sort(low, pi - 1)
            # 递归排序右半部分
            self.quick_sort(pi + 1, high)

# 使用示例
if __name__ == "__main__":
    original_data = [27, 13, 6, 42, 19, 8, 35, 11]
    sorter = QuickSortVisualizer(original_data)
    sorter.quick_sort()
    
    # 打印每一步的状态
    print("排序过程中的完整列表状态：")
    for idx, state in enumerate(sorter.state_log):
        print(f"步骤 {idx+1}: {state}")

关键改动说明 #

• 原地操作：不再生成子列表，而是通过low和high索引限定当前排序的范围，直接修改self.data。
• 状态记录：每次元素交换、基准归位后，都将当前列表的副本存入state_log（必须存副本，否则后续修改会覆盖之前的记录）。
• 分区逻辑：沿用你原本的基准选择（取当前范围最后一个元素），调整为原地交换的分区方式。

针对示例列表的输出 #

对于输入[27, 13, 6, 42, 19, 8, 35, 11]，运行后state_log会包含如下关键状态（部分步骤）：

步骤 1: [13, 27, 6, 42, 19, 8, 35, 11]
步骤 2: [13, 6, 27, 42, 19, 8, 35, 11]
步骤 3: [13, 6, 8, 42, 19, 27, 35, 11]
步骤 4: [13, 6, 8, 11, 19, 27, 35, 42]
步骤 5: [6, 13, 8, 11, 19, 27, 35, 42]
步骤 6: [6, 8, 13, 11, 19, 27, 35, 42]
步骤 7: [6, 8, 11, 13, 19, 27, 35, 42]

（注：你提供的示例中最后一个状态的25应为笔误，正确排序结果对应位置是35）

适配GUI可视化 #

你可以直接从state_log中按顺序取出每一步的列表状态，传递给GUI组件进行绘制（比如用Canvas绘制柱状图），实现排序过程的动态展示。

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