快速排序（Quicksort）能否同时实现稳定和原地排序？

核心结论 #

这个问题的答案取决于你对「原地排序」的定义：

• 如果采用严格定义（仅允许O(1)级别的额外辅助空间，不计入递归调用栈也不允许额外存储下标信息），答案为否，不存在满足要求的快速排序实现，你考试选「是」大概率被判错是符合通用考纲要求的。
• 如果放宽原地定义，允许O(logn)级别的递归栈额外空间，理论上存在可行实现，但这类实现性能极低，没有工业实用价值，也不属于常规快速排序的范畴。

概念澄清 #

首先明确两个术语的通用定义，避免歧义：

• 稳定排序：值相等的元素在排序完成后，依然保持它们在原序列中的相对先后顺序
• 原地排序：算法运行过程中，除输入数据占用的空间外，仅需要常数/对数级别的额外辅助空间，不需要和输入规模成正比的O(n)额外空间

你提到的「额外逻辑」的具体含义 #

你看到的相关表述：

Making it stable either requires order N storage (as in a naive implementation) or a bit of extra logic for an in-place version.

这里提到的原地稳定版本的额外逻辑，指的是用旋转插入操作代替常规快排的交换操作完成分区：
常规快排的分区过程会直接交换两个位置的元素，很容易打乱相等元素的相对顺序；而旋转插入的逻辑是，遇到小于等于基准值的元素时，将当前元素整体旋转插入到已处理的「小于等于基准值区间」的末尾，不会改动区间内原有元素的相对位置，因此可以保证稳定性。

但这类实现有两个无法规避的缺陷：

1. 时间复杂度劣化：常规快排的分区操作为O(n)时间，旋转插入实现的分区操作最坏会让总时间复杂度上升到O(n²)，性能远低于常规快排
2. 额外空间不符合严格原地要求：如果计入递归调用的栈空间，这类实现的额外空间复杂度为O(logn)，如果采用严格O(1)额外空间的定义，它依然不满足原地要求

公开实现少见的原因 #

这类理论可行的原地稳定快排实现没有实用价值，性能比常规快排、归并排序都要差，因此极少有人公开完整的可运行代码，仅会在理论讨论中被提及。

常规考试/算法题场景下，默认采用的是通用工业界/教材的结论：快速排序是原地排序，但天然不稳定，无法同时满足稳定和严格原地的要求，因此你这道题的标准答案应为「否」。

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