AIGC时代算法工程师的面试秘籍（2024.4.29-5.12第十三式） |【三年面试五年模拟】

写在前面

【三年面试五年模拟】旨在整理&挖掘AI算法工程师在实习/校招/社招时所需的干货知识点与面试方法，力求让读者在获得心仪offer的同时，增强技术基本面。也欢迎大家提出宝贵的优化建议，一起交流学习💪

欢迎大家关注Rocky的公众号：WeThinkIn
欢迎大家关注Rocky的知乎：Rocky Ding
获取更多AI行业的前沿资讯与干货资源

大家好，我是Rocky。

《三年面试五年模拟》系列作品帮助很多读者获得了心仪的算法岗offer，收到了大家的很多好评，Rocky觉得很开心也很有意义。

在AIGC时代到来后，Rocky对《三年面试五年模拟》整体战略方向进行了重大的优化重构，在秉持着Rocky创办《三年面试五年模拟》项目初心的同时，增加了AIGC时代核心的版块栏目，详细的版本更新内容如下所示：

整体架构：分为AIGC知识板块和AI通用知识板块。
AIGC知识板块：分为AI绘画、AI视频、大模型、AI多模态、数字人这五大AIGC核心方向。
AI通用知识板块：包含AIGC、传统深度学习、自动驾驶等所有AI核心方向共通的知识点。

Rocky已经将《三年面试五年模拟》项目的完整版构建在Github上：https://github.com/WeThinkIn/Interview-for-Algorithm-Engineer/tree/main，欢迎大家star！

本文是《三年面试五年模拟》项目的第十三式，考虑到易读性与文章篇幅，Rocky本次只从Github完整版项目中摘选了2024年4月29号-2024年5月12号更新的部分经典&干货面试知识点和面试问题，并配以相应的参考答案（精简版），供大家学习探讨。

在《三年面试五年模拟》版本更新白皮书，迎接AIGC时代中我们阐述了《三年面试五年模拟》项目在AIGC时代的愿景与规划，也包含了项目共建计划，感兴趣的朋友可以点击阅读。

当然的，本项目中的内容难免有疏漏与错误之处，欢迎大家在文末评论进行补充优化，Rocky将及时更新完善到Github上！

希望《三年面试五年模拟》能陪伴大家度过整个AI行业的职业生涯，并且让大家能够持续获益。

So，enjoy（与本文的BGM一起食用更佳哦）：

正文开始

目录先行

AI绘画基础：

目前主流的AI绘画大模型有哪些？
SD模型训练时需要设置timesteps=1000，在推理时却只用几十步就可以生成图片？

深度学习基础：

什么是模型微调(fine-tuning)?
深度学习中常用的学习率衰减策略有哪些？

机器学习基础：

什么是奥卡姆剃刀原理？
什么是没有免费的午餐定理？

Python编程基础：

Python中PIL和OpenCV处理图像的区别？
Python中全局变量与局部变量之间的区别？

模型部署基础：

什么是模型蒸馏？
bfloat16精度和float16精度的区别？

计算机基础：

conda创建管理虚拟环境的命令大全
如何让两台服务器之间ssh免密通信？

大厂高频算法题

实现快速排序代码

开放性问题：

AIGC时代的ToC产品开发流程是什么样的？
AIGC时代有哪些可以落地的技术方向？

AI绘画基础

【一】目前主流的AI绘画大模型有哪些？

目前，几个主流的文生图大模型包括：

Midjourney系列（V5-V6）
Stable Diffusion系列（1.x、2.x、XL、3）
DaLL·E系列（2-3）
PixArt系列（α、Σ）
Ideogram 1.0
Playground v2.5
Imagen系列（1、2）

【二】SD模型训练时需要设置timesteps=1000，在推理时却只用几十步就可以生成图片？

目前扩散模型训练一般使用DDPM（Denoising Diffusion Probabilistic Models）采样方法，但推理时可以使用DDIM（Denoising Diffusion Implicit Models）采样方法，DDIM通过去马尔可夫化，大大减少了扩散模型在推理时的步数。

深度学习基础

1、什么是模型微调(fine-tuning)?

在AI行业中，模型微调（Fine-tuning）是一种基础有效的技术，特别适用于迁移学习场景，其中预训练模型的参数被稍作训练调整以适应新的、但与原始训练任务相似的任务。这种方法非常适合于数据量有限的情况，可以显著提高模型的性能和泛化能力。

模型微调的基本步骤：

选择预训练模型：
- 开始微调之前，首先需要一个已经在相关任务上预训练好的模型，通常这些模型在大规模数据集（如ImageNet、Laion等）上进行预训练。因为这些模型已经学习到了丰富的特征表示，可以作为新任务的起点。
初始化：
- 微调时，通常保留预训练模型的大部分或所有权重，作为新任务训练的初始化点。
修改模型结构：
- 根据新任务的需求，可能需要对模型的最后几层进行修改。例如，在图像分类任务中，最后的全连接层（输出层）可能需要根据新任务的类别数进行调整。
重新训练：
- 在新的数据集上继续训练模型。通常只需重新训练模型的一部分，特别是那些针对特定任务调整过的层，而其他层可以保持原始预训练时的参数或者以较小的学习率进行微调，以避免过度拟合。
调整学习率：
- 微调时通常使用比原始预训练时更小的学习率，这有助于保持已经学习到的有用特征，并仅对它们进行精细的调整。

模型微调的应用场景：

AIGC：AI绘画、AI视频、大模型、AI多模态、数字人、AI音频等。
传统深度学习：图像分类、图像分割、目标检测、目标跟踪等。
自动驾驶：车载图像分类、车载图像分割、车载目标检测等。

微调的好处：

加速训练：由于模型从有效的初始状态开始学习，微调通常比从头开始训练快得多。
需要更少的数据：微调可以在相对较少的数据上进行，因为模型已经从预训练中获得了大量的通用知识。
提高性能：通过利用预训练模型的知识，可以提高模型在新任务上的表现，特别是当新任务的数据不足以从头开始训练复杂模型时。

总的来说，模型微调是一种高效利用已有知识以适应新任务的方法，特别适用于数据资源有限的场景。

2、深度学习中常用的学习率衰减策略有哪些？

在AI领域中，合适的学习率调整策略对于模型的训练效果和收敛速度至关重要。

学习率衰减（或调整）是用来在训练过程中逐步减小学习率的方法，目的是帮助模型更好地收敛，避免训练过程中的振荡或不稳定。

以下是几种常用的学习率衰减方法：

1. 固定学习率衰减

这是最简单的衰减方法之一，其中学习率按预定的固定间隔和固定因子进行减少。例如，每过10个epoch将学习率乘以0.1。

2. 指数衰减

在指数衰减模式下，学习率按照指数函数逐步减小，通常定义为：
$\text{Learning Rate} = \text{Initial Learning Rate} \times e^{-\text{decay rate} \times \text{epoch}}$
其中，decay rate是一个预先设定的常数，epoch是当前的训练轮数。

3. 时间基衰减

时间基衰减与指数衰减类似，但学习率的衰减与训练的具体时间（通常是epoch数）更直接相关：
$\text{Learning Rate} = \frac{\text{Initial Learning Rate}}{1 + \text{decay rate} \times \text{epoch}}$

4. 阶梯衰减

在阶梯衰减中，学习率在一系列预设的epoch（如每20个epoch）后显著下降。这种衰减通常是手动设置的，非常直观，允许模型在较高的学习率下快速学习，并在训练后期通过较低的学习率细化模型。

5. 余弦衰减

余弦衰减是一种较新的策略，它模仿了余弦函数的形状来调整学习率，从初始学习率逐渐减小到接近零的值。这种方法在一些周期性或重启的训练策略中特别有效，可以帮助模型跳出局部最小值。

6. 适应性学习率方法

这包括像Adam和RMSprop这样的优化算法，这些算法本身就能够调整每个参数的学习率，通常基于历史梯度的平方（用于归一化梯度）。这些方法自动调整学习率，无需显式的衰减策略。

7. 热身和重启

学习率热身：在训练初期，学习率从一个较低的值逐渐增加到设定的初始学习率。这有助于模型在训练初期稳定下来，防止初始学习率过高导致的不稳定。
周期性重启：学习率按周期性地增加和减少，每次“重启”都从较高的学习率开始，然后再次衰减。这种方法有助于模型跳出局部最小值，寻找更好的全局最小值。

这些学习率调整方法可以单独使用，也可以结合使用，以达到最佳的训练效果。选择哪种衰减策略取决于具体任务、模型的复杂性以及训练数据的特点。在实际应用中，通常需要通过多次实验来确定最合适的学习率调整策略。

机器学习基础

1、什么是奥卡姆剃刀原理？

在机器学习领域中，奥卡姆剃刀（Occam’s Razor）原理是一个重要的理论指导原则，通常被表述为：“面对一个具体问题，选择最合适和最简单的能够满足需求的算法模型。”

这一原则来源于14世纪的逻辑学家威廉·奥卡姆，他主张：“如无必要，勿增实体。”

这在传统深度学习领域已经经过大量的验证，比如说图像分类领域的ResNet、图像分割领域的U-Net、目标检测领域的YOLO，这些都是能够跨过周期的AI算法模型，都具备简洁、稳定、高效等特点。

奥卡姆剃刀在机器学习领域中的应用

在机器学习模型的设计和训练过程中，奥卡姆剃刀原则可以解释为：当两个或多个不同复杂度的模型都能够合理地解释或预测数据时，应选择最简单的那个。这一原则的应用主要体现在以下几个方面：

模型的泛化能力：简单的模型通常比复杂的模型更容易泛化到未见过的新数据上。复杂的模型可能会在训练数据上表现得非常好，但可能会因为过拟合而在新数据上表现不佳。
避免过拟合：在选择模型时，遵循奥卡姆剃刀原则有助于减少过拟合的风险。简单模型在参数少和结构简单的情况下，对数据的噪声和偶然的特征不那么敏感。
计算效率：简单模型通常计算需求较低，更快速且易于部署。在资源受限的环境中，如移动设备或嵌入式系统中，简单模型尤其受到青睐。
可解释性：简单模型通常更容易被理解和解释。在需要对模型的性能进行解释的领域（如金融、医疗等领域）中，简单模型可能更受欢迎。

如何实现奥卡姆剃刀原则

在实践中，实现奥卡姆剃刀原则可以通过以下策略：

深入理解应用长颈：只有深入理解实际场景，在能够知道其中的特点与痛点，才能高屋建瓴为算法解决方案与产品的构建提供指导思想。
选择合适的算法模型：根据实际场景，选择适当复杂度的模型。
使用优化技巧：在模型训练过程中使用正则化项、修改模型部分结构等方法，来优化模型性能。
交叉验证：使用交叉验证来评估不同模型的性能，帮助选择最合适的模型。

总之，奥卡姆剃刀原则是一种有助于指导机器学习领域的算法工程师工作的哲学思想，它鼓励我们针对实际场景寻找最简洁的算法模型。在模型选择和开发过程中恰当地应用这一原则，可以帮助开发出既有效又高效的机器学习算法解决方案。

2、什么是没有免费的午餐定理？

在机器学习和优化领域，没有免费的午餐定理（No Free Lunch Theorem, NFL)是一个非常重要的概念，由David Wolpert和William Macready在1997年首次提出。

这个定理深刻地表述了机器学习领域一个看似简单却深刻的观点：所有的优化算法在所有可能的问题上的平均性能都是相同的。

定理的基本内容

没有免费的午餐定理主要针对机器学习算法和优化搜索算法，它表明没有任何一个算法能在所有可能的问题上都表现得比其他算法更好。

换句话说，一个算法如果在某类问题上表现出色，那么必然存在另一类问题，在那里它的表现就不那么理想。这意味着机器学习算法的效果很大程度上依赖于它所应用的细分领域与具体问题（具体问题具体分析）。

更深层次的挖掘，Rocky认为NFL定理告诉我们，在机器学习领域，所有的行为与优化，都是“有得必有失的”，这个哲学思想也可以让算法工程师们破圈，不仅仅用于AI行业。

Python编程基础

1、Python中PIL和OpenCV处理图像的区别？

Python中的Pillow/PIL（Python Imaging Library）和OpenCV（Open Source Computer Vision Library）都是强大的图像处理库，但它们各有特点和优势，适用于不同的应用场景。

以下是两者之间的详细对比：

数据类型：Pillow读取图像时返回的是PIL.Image.Image类型的对象。而OpenCV读取图像时返回的是NumPy数组。
颜色格式：OpenCV默认使用BGR颜色格式读取图像。而Pillow使用的是更常见的RGB格式。
应用专长：Pillow主要专注于图像的加载、处理和保存，提供了广泛的图像处理能力，如图像缩放、裁剪、过滤、图像合成等，更加侧重于图像处理的基本操作和图像的IO操作。OpenCV是一个专注于实时计算机视觉的库，它的功能不仅限于图像处理，还包括视频处理、人脸识别、对象检测、复杂图像分析等，适用于需要快速有效处理大量数据的应用。
性能和效率：对于高性能的实时计算机视觉任务，OpenCV通常比Pillow表现得更好，因为OpenCV底层使用了优化的C++代码，同时支持多线程和GPU加速。在常规图像处理任务中，Pillow更易于使用，且对于基本的图像处理任务已经足够快，并且易于集成到Python应用中。

总结

Pillow适合于需要处理图像文件、执行基本图像处理任务的应用，而OpenCV适合于需要实施复杂的图像分析、计算机视觉处理或实时视频处理的项目。选择哪个库取决于你的具体需求、项目复杂度以及性能要求。

2、Python中全局变量与局部变量之间的区别？

在Python中，全局变量和局部变量的区别主要体现在变量的作用域、声明位置以及在程序中的可访问性上。理解这些差异有助于我们更好地管理数据的流向和变量的生命周期，防止不必要的编程错误。

全局变量

定义与作用域：
- 全局变量是在函数外部定义的，其作用域覆盖了整个代码文件/定义它的模块。
- 在任何函数内部和外部都可以访问全局变量（除非被局部作用域的同名变量遮蔽）。
使用场景：
- 当多个函数需要访问同一数据时，可以使用全局变量。
- 用于定义整个应用程序可能需要的配置信息或共享数据。

局部变量

定义与作用域：
- 局部变量是在函数内部/代码块中定义的，它只在定义它的函数或代码块内部有效。
- 函数或代码块执行完毕后，局部变量的生命周期结束，它们所占用的内存也随之释放。
使用场景：
- 当变量的用途仅限于特定函数或代码块时，应使用局部变量。
- 局部变量有助于保持函数的独立性，使函数更易理解和重用。
优势：
- 局部变量避免了函数间的数据交互问题，减少了代码的耦合度。
- 使用局部变量可以提高代码的可读性和维护性。

访问和修改全局变量

在Python中，如果你需要在一个函数内部修改全局变量，你必须使用global这个全局关键字来进行声明：

x = 10  # 全局变量

def update():
    global x
    x = 20  # 修改全局变量

def print_x():
    print(x)  # 访问全局变量

update()
print_x()  # 输出: 20

如果不使用global全局关键字，对全局变量的修改实际上会创建一个同名的新的局部变量，而不会改变全局变量的值。

模型部署基础

1、什么是模型蒸馏？

模型蒸馏（Model Distillation）是一种模型压缩技术，旨在将一个**大型复杂模型（通常称为“教师模型”）的知识转移到一个小型简单模型（称为“学生模型”）**中。

模型蒸馏技术最开始由Hinton等人于2015年提出，主要用于改进小型模型的性能，使其在保持较低计算成本的同时，能够逼近大型模型的性能。

模型蒸馏的基本原理

模型蒸馏的基本思想是使用大型模型的输出（软标签）来训练小型模型。

大型模型的输出通常包含了关于类别概率的更多信息，这些信息比硬标签（即实际的类别标签）更能表达不同类别之间的相对关系。通过训练小型模型去学习逼近这些软标签，小型模型可以学习到更细致的决策边界。

模型蒸馏的步骤

训练教师模型：
教师模型通常是一个大型深度网络，能够在AI细分任务上达到SOTA精度。
生成软标签：
使用教师模型对训练数据集进行预测，记录输出的类别概率（软标签）。这些概率不仅表示最可能的类别，还提供了对其他类别的预测概率，包含了更丰富的信息。
训练学生模型：
学生模型的结构比教师模型简单，其训练过程不仅使用真实的标签（硬标签），还使用教师模型生成的软标签。通常，训练过程中会使用一个**温度参数（T）**来调整软标签的"软化"程度。损失函数是硬标签的损失和软标签的损失的加权和。
评估学生模型：
在独立的测试数据上评估学生模型的性能，验证其是否成功学习到了教师模型的知识。

温度调整（Temperature Scaling）

在蒸馏过程中，温度参数T用于控制软标签的平滑程度。较高的温度会使得概率分布更加平滑，使得学生模型能够从教师模型的预测中学到更细微的差别。损失函数通常是交叉熵损失，计算学生模型预测和软标签之间的差异。

模型蒸馏的优势

效率提升：学生模型通常比教师模型更小、更快，适合部署在资源受限的环境中。
泛化能力：学生模型通过学习教师模型的软标签，通常可以获得比直接训练更好的泛化能力。

实际应用

模型蒸馏已被广泛应用于多种任务，如AI绘画、图像分类、图像分割、目标检测、语音识别和自然语言处理等，特别是在需要模型部署到移动设备或需要实时处理的场景中。

总之，模型蒸馏是提高模型部署效率的有效技术，特别适合于需要在保持模型性能的同时减小模型大小和提升计算速度的应用场景。

2、bfloat16精度和float16精度的区别？

BFLOAT16

定义与结构：
BFLOAT16是一种16位宽的浮点数格式，由Google针对Tensor Processing Units (TPUs)开发，特别适用于AI算法应用。它的结构如下：

1位符号位
8位指数
7位尾数

这种格式与标准的32位浮点数（FP32）共享相同的指数范围，但尾数精度较低。这意味着BFLOAT16在表示大范围数值时与FP32相近，但在表示精度上有所折衷。

优点：

较大的动态范围：与Float16相比，BFLOAT16能够表示更大范围的数值，这归功于它更大的指数范围。这对于深度学习中的梯度和归一化运算非常重要，因为这些操作可能涉及广泛的数值范围。
与FP32兼容性好：由于指数位与FP32相同，BFLOAT16可以无损地转换为FP32，这简化了混合精度训练的实现，同时减少了转换过程中的精度损失。

缺点：

较低的数值精度：因为尾数位只有7位，相比于Float16的10位尾数，BFLOAT16在表示精确数值时的能力较弱。

Float16(FP16)

定义与结构：
Float16是IEEE定义的16位浮点数标准，结构如下：

1位符号位
5位指数
10位尾数

Float16提供了较FP32更低的精度和较小的数值范围，但在存储和计算效率上具有优势。

优点：

较高的数值精度：Float16的10位尾数提供了比BFLOAT16更高的精度，适合需要高精度计算的应用。
计算加速：在支持Float16运算的硬件上（如GPU），使用Float16可以显著加速计算过程，尤其是在AI模型训练和推理中。

缺点：

较小的动态范围：Float16的5位指数提供的动态范围较小，可能导致在一些AI训练场景中出现梯度消失或爆炸问题。
兼容性问题：Float16到FP32的转换可能会涉及更复杂的数值调整，可能导致精度损失。

应用场景

BFLOAT16：由于其较大的动态范围和与FP32的良好兼容性，非常适合用于AI模型的训练和推理，尤其是在Google的TPU上。
Float16：适用于对计算精度要求较高的场景，并且在NVIDIA及其他厂商的GPU上得到了广泛支持，尤其适合于需要加速的AI算法任务。

计算机基础

Rocky从工业界、应用界、竞赛界以及学术界角度出发，总结沉淀AI行业中需要用到的实用计算机基础知识，不仅能在面试中帮助到我们，还能让我们在日常工作中提高效率。

1、conda创建管理虚拟环境的命令大全

在AIGC时代，各种AI工作流飞速繁荣，我们要做好每个工作流与算法解决方案的环境配置与隔离，避免冲突，以免导致日常工作中的思维混乱。

Conda是一个主流的包管理器和环境管理器，常用于数据科学、机器学习和科学计算领域。使用Conda可以轻松地创建、管理和共享虚拟环境，下面是Conda在虚拟环境管理方面的一些常用命令：

创建虚拟环境

创建新的虚拟环境：
```
conda create -n myenv
```
这会创建一个名为 myenv 的新虚拟环境。
指定Python版本：
```
conda create -n myenv python=3.8
```
创建一个包含特定 Python 版本（例如 Python 3.8）的虚拟环境。
- 指定环境保存地址：
```
conda create -p /本地路径/myenv python=3.8
```

激活和停用虚拟环境

激活虚拟环境：
```
conda activate myenv
```
激活名为 myenv 的虚拟环境。
停用虚拟环境：
```
conda deactivate
```
停用当前激活的虚拟环境。

管理虚拟环境中的包

安装包：
```
conda install numpy
```
在当前激活的环境中安装包（例如安装 NumPy）。
列出环境中的包：
```
conda list
```
显示当前环境中安装的所有包。
更新包：
```
conda update numpy
```
更新当前环境中的特定包（例如 NumPy）。
卸载包：
```
conda remove numpy
```
从当前环境中卸载特定的包。

管理环境

列出所有虚拟环境：
```
conda env list
或者
conda info --envs
```
这些命令显示所有已创建的虚拟环境。
复制虚拟环境：
```
conda create -n myenv2 --clone myenv
```
创建一个名为 myenv2 的新环境，这是 myenv 的完整副本。
删除虚拟环境：
```
conda remove -n myenv --all
```
删除名为 myenv 的虚拟环境。
导出环境到文件：
```
conda env export > environment.yml
```
将当前环境的所有包导出到 environment.yml 文件中，便于再现环境。
从文件创建环境：
```
conda env create -f environment.yml
```
根据 environment.yml 文件创建虚拟环境。

这些命令为使用Conda管理虚拟环境提供了全面的控制，使得在不同项目之间隔离依赖关系和环境配置变得简单。这对于确保项目的可重现性和避免依赖冲突非常重要。

2、如何让两台服务器之间ssh免密通信？

在Ubuntu系统中设置基于SSH密钥的认证，可以在两台服务器之间进行无密码连接。这对于自动化任务（如文件传输、备份和远程命令执行）特别有用。以下是设置SSH密钥认证的步骤：

假定有2台Linux服务器主机，分别为A，B。

我们先在所有服务器主机上创建ssh目录并赋予权限:

mkdir /root/.ssh 
chmod 700 /root/.ssh

生成公钥与私钥

我们接着需要生成所有服务器主机的公钥与私钥，执行以下命令：

$ cd ~  # 进⼊入用户目录
$ ssh-keygen -t rsa -P ""  # 生成ssh密码，-t 参数表示生成算法，可以选择rsa和dsa；-P表示使用的密码，""表示无密码。

将公钥追加authorized_keys文件中

将第一台服务器主机A上生成公钥追加到authorized_keys文件中:

$ cd ~/.ssh  # 进入.ssh目录
$ cat id_rsa.pub >> authorized_keys   # 将id_rsa.pub的内容追加到authorized_keys文件中

接下来我们使用同样的命令在服务器主机B上生成id_rsa.pub并写入到服务器主机A的authorized_keys文件中，再将服务器主机A的authorized_keys文件复制到服务器主机B的对应路径下即可：/root/.ssh/

大厂高频算法题

1、实现快速排序代码

快速排序（Quick Sort）是一种高效的排序算法，由C. A. R. Hoare在1960年提出。它是一种分治法（Divide and Conquer）策略的典型应用。

快速排序的原理：

选择基准值（Pivot）：
快速排序首先从数组中选择一个元素作为基准值，这个值称为“pivot”。选择的方法可以多样，如选择第一个元素、最后一个元素、中间元素或随机元素。
分区操作：
数组被分为两个部分，使得：
- 左边部分的所有元素都不大于基准值，
- 右边部分的所有元素都不小于基准值。
此时，基准值处于整个数组中的最终位置。
递归排序：
递归地对基准左侧和右侧的两个子数组进行快速排序，直到子数组的长度为1或0，此时数组已经完全排序。

快速排序主要有两种实现方式，分别是递归方式和迭代方式。

下面我们首先来看一下递归方式实现的快速排序的代码：

Python代码实现（递归版本）：

以下是快速排序的一个简单Python实现，其中使用了Lomuto分区方案：

def quick_sort(arr):
    def partition(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 quick_sort_recursive(low, high):
        if low < high:
            pi = partition(low, high)
            quick_sort_recursive(low, pi - 1)
            quick_sort_recursive(pi + 1, high)

    quick_sort_recursive(0, len(arr) - 1)
    return arr

# 测试用例
test_cases = [
    [10, 7, 8, 9, 1, 5],
    [1, 2, 3, 4, 5],
    [5, 4, 3, 2, 1],
    [],
    [1],
    [11, 11, 11, 11]
]

# 展示排序结果
for case in test_cases:
    print(f"Original: {case}")
    print(f"Sorted: {quick_sort(case)}\n")

# 代码运行结果
Original: [10, 7, 8, 9, 1, 5]
Sorted: [1, 5, 7, 8, 9, 10]

Original: [1, 2, 3, 4, 5]
Sorted: [1, 2, 3, 4, 5]

Original: [5, 4, 3, 2, 1]
Sorted: [1, 2, 3, 4, 5]

Original: []
Sorted: []

Original: [1]
Sorted: [1]

Original: [11, 11, 11, 11]
Sorted: [11, 11, 11, 11]

测试用例及其输出：

上面的代码对包含多种情况的测试用例进行了排序，包括：

普通未排序数组，
已排序数组，
逆序数组，
空数组，
单元素数组，
所有元素相同的数组。

这些测试用例涵盖了快速排序可能面临的一些典型情况，并显示了算法处理这些情况的能力。每个测试用例的输出将展示原始数组和排序后的数组，以验证排序过程的正确性。

非递归（迭代）版本的快速排序可以使用一个显式的栈来模拟递归过程。这种方法避免了递归可能带来的栈溢出问题，并直观地展示了算法的控制流程。下面是如何使用栈实现快速排序的迭代版本：

Python代码实现（迭代版本）：

def quick_sort_iterative(arr):
    if arr == []:
        return arr
    # 创建一个栈
    stack = []
    # 初始范围从0到数组长度减一
    stack.append(0)
    stack.append(len(arr) - 1)

    # 只要栈非空，就继续运行
    while stack:
        # 弹出 high 和 low
        high = stack.pop()
        low = stack.pop()

        # 使用Lomuto分区方案
        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]
        # 交换pivot到正确位置
        i += 1
        arr[i], arr[high] = arr[high], arr[i]
        pi = i

        # 如果有左子数组，将其范围入栈
        if pi - 1 > low:
            stack.append(low)
            stack.append(pi - 1)
        
        # 如果有右子数组，将其范围入栈
        if pi + 1 < high:
            stack.append(pi + 1)
            stack.append(high)

    return arr

# 测试用例
test_cases = [
    [10, 7, 8, 9, 1, 5],
    [1, 2, 3, 4, 5],
    [5, 4, 3, 2, 1],
    [],
    [1],
    [11, 11, 11, 11]
]

# 展示排序结果
for case in test_cases:
    print(f"Original: {case}")
    print(f"Sorted: {quick_sort_iterative(case)}\n")

# 代码运行结果
Original: [10, 7, 8, 9, 1, 5]
Sorted: [1, 5, 7, 8, 9, 10]

Original: [1, 2, 3, 4, 5]
Sorted: [1, 2, 3, 4, 5]

Original: [5, 4, 3, 2, 1]
Sorted: [1, 2, 3, 4, 5]

Original: []
Sorted: []

Original: [1]
Sorted: [1]

Original: [11, 11, 11, 11]
Sorted: [11, 11, 11, 11]

在迭代版本的快速排序中，我们使用了栈来保存将要处理的子数组的索引。这种方法模拟了递归调用栈的行为：

首先，将整个数组的起始和结束索引推入栈中。
然后，使用一个循环，直到栈为空，在每次迭代中：
- 从栈中弹出一个子数组的界限（high 和 low）。
- 执行分区操作，确定 pivot 的最终位置。
- 根据 pivot 的位置，决定是否将左子数组或右子数组的索引范围推回栈中。

这种迭代方法避免了递归的深度调用，特别是对于那些可能导致递归深度很深的大数组来说，是一个更稳定的选择。

迭代版本的快速排序在时间复杂度和空间复杂度上的表现与递归版本相似，但有一些关键的实现细节差异：

时间复杂度

最佳和平均情况：对于平均分布的数据，快速排序的时间复杂度通常是 $\log n)$ 。这是因为每次分区大约将数组分成两半，需要递归或迭代地应用这一过程大约 $\log n$ 次。
最坏情况：在最坏的情况下，如果每次选择的基准都是最小或最大的元素，快速排序的时间复杂度会退化到 $O(n^2)$ 。这种情况在数组已经基本有序的情况下可能发生（完全正序或完全逆序），每次分区操作只能减少一个元素。

空间复杂度

递归版本：递归版本的快速排序在最坏情况下的空间复杂度可以达到 $O (n)$ ，这是由递归调用栈深度决定的。在平均情况下，由于递归的深度接近 $\log n$ ，其空间复杂度是 $O(\log n)$ 。
迭代版本：迭代版本使用一个显式的栈来存储未处理的子数组的界限。虽然这避免了函数调用的开销，但栈的空间使用仍然可以在最坏情况下达到 $O (n)$ ，特别是当数组几乎有序时，可能需要将许多小的子数组范围推入栈。在平均情况下，空间复杂度通常也是 $O(\log n)$ ，因为每次都将数组大致分成两部分。