请手写快速排序，并分别用递归和迭代两种方式实现。

回答思路

1. 正确实现递归快速排序并讲解分治思想
2. 能写出迭代版本并说明递归转迭代的关键（栈模拟）
3. 分析分区（partition）逻辑、枢轴（pivot）选择和边界条件
4. 说明平均与最坏时间复杂度